动态规划——背包问题（C语言）_背包问题[动态规划]代码

背包问题一般也是很难去理解，最主要的是理解思路

废话不多说，直接开始。

首先可以理解为像是一个树一样；

左子树为拾取，右子树为不拾取

假如背包容量为 8。然后有以下一些物品 

类似于这样：

以下是C语言代码实现，注释已写

#include<stdio.h>
#include<stdlib.h>
 
/*val是物品的价值，v为物品的体积，dp第一个是物品的下标
* 第二个是物品的体积，意为价值
* 
*/
 
int val[1001], v[1001], dp[1001][1001] = { 0 };
int n, V;
int Max(int a, int b)							//判断大小
{
	return a > b ? a : b;
}
void backpack() {
	for (int i = v[0]; i <= V; i++) {
		dp[0][i] = val[0];						//当背包容量大于物品容量时，放入物品0
	}
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= V; j++) {			//先便利物品再遍历体积
 
			if(j<v[i])							//！！！！！当前！！！！背包体积小于物体体积
				dp[i][j]=dp[i-1][j];			//不放入，并且把空的全部填上i-1物品的价值
			else
			{
				dp[i][j] = Max(dp[i-1][j],dp[i-1][j-v[i] ]+ val[i]);
 
				//比较放入之前与放入之后的价值；
				//j-v[i]表示放了物品i，还剩下j-v[i]的容量
				//放之后的价值  =    放之前的价值+物品i的价值
				//dp[i-1][j-v[i]],表示不放物品i时的价值
				//看是装下这个物品的价值大还是不装下价值大（与i-1物品进行比较）
 			}
		}
	}
}
int main()
{
	scanf("%d%d", &n, &V);
	for (int i = 0; i < n; i++)
		scanf("%d %d", &v[i], &val[i]);
	backpack();
	printf("%d", dp[n][V]);
	return 0;
}