当前位置:   article > 正文

完全背包问题(动态规划(DP))

完全背包问题

原题

完全背包问题

有n种重量和价值分别为wi,vi的物品。从这些物品中挑选总重量不超过W的物品,求出挑选物品价值总和的最大值。在这里,每种物品可以挑选任意多件。
1<=n<=100
1<=wi,vi<=100
1<=W<=10000

样例输入


n=3

(w,v)={(3,4),(4,5),(2,3)}

W=7


样例输出


10(0号物品选1个,2号物品选2个)

涉及知识及算法


递推关系:
dp[0][j]=0
dp[i+1][j]=max{dp[i][j-k*w[i]]+k*v[i]|0<=k}
但直接这样去写程序是三重循环,时间复杂度为O(mW^2).
在这个算法中有多余的计算:
在dp[i+1][j]的计算中选择k(k>=1)个 i 物品的情况,与在dp[i+1][j-w[i]]的计算中选择k-1的情况是相同的,所以dp[i+1][j]的递推中k>=1部分的计算已经在dp[i+1][j-w[i]]的计算中完成了。那么可以按照如下方式进行变形:
dp[i+1][j]
=max{dp[i][j-k*w[i]]+k*v[i]|0<=k}
=max(dp[i][j],max{dp[i][j-k*w[i]]+k*v[i]|1<=k})
=max(dp[i][j],max{dp[i][(j-w[i])-k*w[i]]+k*v[i]|0<=k}+v[i])
=max(dp[i][j],dp[i+1][j-w[i]]+v[i])
这样一来就可以用O(nW)时间解决问题。

代码

  1. void solve()
  2. {
  3. for(int i=0;i<n;i++)
  4. {
  5. for(int j=0;j<=W;j++)
  6. {
  7. if(j<w[i])
  8. {
  9. dp[i+1][j]=dp[i][j];
  10. }
  11. else
  12. {
  13. dp[i+1][j]=max(dp[i][j],dp[i+1][j-w[i]]+v[i]);
  14. }
  15. }
  16. }
  17. printf("%d\n",dp[n][W]);
  18. }

此外,之前提到的01背包问题和这里的完全背包问题,可以通过不断重复利用一个数组来实现。
01背包问题的情况
  1. void solve()
  2. {
  3. for(int i=0;i<n;i++)
  4. {
  5. for(int j=W;j>=w[i];j--)
  6. {
  7. dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
  8. }
  9. }
  10. printf("%d\n",dp[w]);
  11. }
完全背包问题的情况
  1. int dp[MAX_W+1];
  2. void solve()
  3. {
  4. for(int i=0;i<n;i++)
  5. {
  6. for(int j=w[i];j<=W;j++)
  7. {
  8. dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
  9. }
  10. }
  11. printf("%d\n",dp[w]);
  12. }
注:文章转载自《挑战程序设计竞赛》(第二版)


本文内容由网友自发贡献,转载请注明出处:https://www.wpsshop.cn/w/人工智能uu/article/detail/833631
推荐阅读
相关标签
  

闽ICP备14008679号