输入:
n=3
(w,v)={(3,4),(4,5),(2,3)}
W=7
输出:
10(0号物品选1个,2号物品选2个)
和01背包的区别是物品可以任意选择.
令dp[i+1][j]=从前i种物品中挑选任意总重量不超过j时总价值的最大值.那么递推关系为:
dp[0][j]=0
dp[i+1][j]=max{dp[i-k*w[i]]+k*v[i]|0<=k}
=max{dp[i][j-k*w[i]]+k*v[i]|0<=k}
1 int dp[MAX][MAX]; //DP数组 2 3 void solve() 4 { 5 for(int i=0; i<n; i++){ 6 for(int j=0; j<=W; j++){ 7 for(int k=0; k*w[i]<=j; k++){ 8 dp[i+1][j]=max(dp[i+1][j],dp[i][j-k*w[i]]+k*v[i]); 9 } 10 } 11 } 12 printf("%d\n",dp[n][m]); 13 }
复杂度为:O(nW2)
修改后:
1 void solve() 2 { 3 for(int i=0; i<n; i++){ 4 for(int j=0; j<=W; j++){ 5 if(j<w[i]){ 6 dp[i+1][j]=dp[i][j]; 7 } 8 else{ 9 dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]); 10 } 11 } 12 } 13 printf("%d\n",dp[n][W]); 14 }
复杂度:O(nW)
当然,01背包和完全背包可以通过不断重复利用一个数组来实现.
01背包问题的情况:
1 int dp[MAX]; //DP数组 2 3 void solve() 4 { 5 for(int i=0; i<n; i++){ 6 for(int j=W; j>=w[i]; j--){ 7 dp[i]=max(dp[j],dp[j-w[i]+v[i]]); 8 } 9 } 10 printf("%d\n",dp[W]); 11 }
完全背包问题的情况:
1 int dp[MAX]; //DP数组 2 3 void solve() 4 { 5 for(int i=0; i<n; i++){ 6 for(int j=w[i]; j<=W; j++){ 7 dp[i]=max(dp[j],dp[j-w[i]+v[i]]); 8 } 9 } 10 printf("%d\n",dp[W]); 11 }
两者的差异就变成只有循环方向.重复利用数组虽然可以节省内存空间,但是得不好将有可能留下bug,所以要格外小心.不过出于节约内存的考虑,有时候必须要重读利用数组.也存在通过重复利用能够进一步降低复杂度的问题.
DP数组的再利用:
可以通过讲两个数组滚动使用来实现重复利用.
dp[i+1][j]=max(dp[i][j],dp[i+1][j-w[i]]+v[i])
dp[i+1]计算时只需要dp[i]和dp[i+1],所以可以结合奇偶性写成如下形式:
1 int dp[2][MAX]; //DP数组 2 3 void solve() 4 { 5 for(int i=0; i<n; i++){ 6 for(int j=0; j<=W; j++){ 7 if(j<w[i]){ 8 dp[(i+1)&1][j]=dp[i&1][j]; 9 } 10 else{ 11 dp[(i+1)&1][j]=max(dp[i&1][j],dp[(i+1)&1][j-w[i]]+v[i]); 12 } 13 } 14 } 15 printf("%d\n",dp[n&1[W]); 16 }
<<挑战程序设计竞赛>>读后感
原文：http://www.cnblogs.com/wangmengmeng/p/5232491.html