完全背包 (DP)

输入:

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}

 int dp[MAX][MAX];  //DP数组

 void solve()

 {

     for(int i=; i<n; i++){

         for(int j=; j<=W; j++){

             for(int k=; k*w[i]<=j; k++){

                 dp[i+][j]=max(dp[i+][j],dp[i][j-k*w[i]]+k*v[i]);

             }

         }

     }

     printf("%d\n",dp[n][m]);

 }

复杂度为:O(nW²)

修改后:

 void solve()

 {

     for(int i=; i<n; i++){

         for(int j=; j<=W; j++){

             if(j<w[i]){

                 dp[i+][j]=dp[i][j];

             }

             else{

                 dp[i+][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);

             }

         }

     }

     printf("%d\n",dp[n][W]);

 }

复杂度:O(nW)

当然,01背包和完全背包可以通过不断重复利用一个数组来实现.

01背包问题的情况:

 int dp[MAX];  //DP数组

 void solve()

 {

     for(int i=; i<n; i++){

         for(int j=W; j>=w[i]; j--){

             dp[i]=max(dp[j],dp[j-w[i]+v[i]]);

         }

     }

     printf("%d\n",dp[W]);

 }

完全背包问题的情况:

 int dp[MAX];  //DP数组

 void solve()

 {

     for(int i=; i<n; i++){

         for(int j=w[i]; j<=W; j++){

             dp[i]=max(dp[j],dp[j-w[i]+v[i]]);

         }

     }

     printf("%d\n",dp[W]);

 }

两者的差异就变成只有循环方向.重复利用数组虽然可以节省内存空间,但是得不好将有可能留下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],所以可以结合奇偶性写成如下形式:

 int dp[][MAX];  //DP数组

 void solve()

 {

     for(int i=; i<n; i++){

         for(int j=; j<=W; j++){

             if(j<w[i]){

                 dp[(i+)&][j]=dp[i&][j];

             }

             else{

                 dp[(i+)&][j]=max(dp[i&][j],dp[(i+)&][j-w[i]]+v[i]);

             }

         }

     }

     printf("%d\n",dp[n&[W]);

 }

<<挑战程序设计竞赛>>读后感

巴特西

完全背包 (DP)

最新文章

热门文章