动态规划-背包是否装满

很简单但是需要特别注意的，一定不要错。

背包：
有n 种不同的物品，每个物品有两个属性，v体积，c价值，现在给一个体积为 m 的背包，问最多可带走多少价值的物品。
      状态转移方程  dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+c[i])
dp[i-1][j]表示不放第i件物品的最大价值，dp[i-1][j-v[i]]+c[i]表示放第i件物品的最大价值；[i-1][j-v[i]]这个表示将    前i-1件物品放入空间为  j-v[i] 的背包中的最大价值。为啥要j-v[i] ？因为要放第i件物品，所以所剩空间就剩了      j-v[i].  所以[i-1][j-v[i]]+c[i]就表示放第i件物品的最大价值。

（1）背包不一定装满。
dp[j]记录的是前i件物品放入空间为j的背包中的最大价值！！！
要在一开始，让dp[1001]中的每个值为 0;

（2）背包刚好装满    

背包刚好装满需要注意：

要把f[j]  (表示刚好装满的最大价值) 这样初始化！

f[0]=0; f[1~n]=负无穷-inf

（注意：codeblocks中没有直接表示无穷的符号，inf是自己定义的）

因为这样就能是那些能够恰好装满背包的物品的值为正数！而那些不能恰好装满背包的物品 的值就为负数。

这样就容易区分了。

这样dp（n）（背包最多承重） == inf话，说明装不满，装满的话 如果要求装满最多的价值，直接输出dp【n】

最后

以上就是糊涂小虾米为你收集整理的动态规划-背包是否装满的全部内容，希望文章能够帮你解决动态规划-背包是否装满所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。