DP之完全背包问题

完全背包：

Such as：设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。

 

对于这个问题，啊，还是直接上代码吧，在代码中理解，

解一：

只需在01背包上稍稍改善以下就行

 

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
    int dp[20][20],x[20];
    int v[]={0,8,10,6,3,7,2}; ///为便于读者阅读，初始化
    int w[]={0,4,6,2,2,5,1};
    int n=6,c=12;

    memset(dp,0,sizeof(dp)); ///小提醒：只能赋0，或-1
    for(int i=1;i<=n;i++)  ///从第1个到第i个物品中挑选出总重量不超过j的物品时总价值的最大值
    {
        for(int j=1;j<=c;j++)
        {
        for(int k=1;k*w[i]<=j;k++){ ///跟01背包就只多了这一句，应该都很好理解，这里就不多解释了。
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*w[i]]+k*v[i]);
            }
        }
    }
    printf("%d\n",dp[n][c]); ///总价值
   return 0;

}

解二：

这样写的的程序有三重循环，显然复杂度有点大哦，其实我们还可以优化，怎么优化呢？看这里，我们在dp[i][j]的计算中选择k(k>=1)个的情况，与在dp[i+1][j-w[i]]的计算中选择k-1个的情况是一样的，，这样我们就不需要k变量循环语句了，所以我们就可以这样敲：

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

dp[i][j-w[i]]=max(dp[i-1][j],dp[i][j-2*w[i]]+2*v[i]);    k-2个；此次其实已经在k-1个之前算出来了（因为j是从1到c的，k-2个的j-2*w[i]值是不是肯定小于k-1个的j-w[i]的值，所以就能很好的解释为什么k-2个在k-1个之前已经算出来了），我们就是通过这样类似于解法1的循环去解出来的，紧接着还有k-3个，也在k-2个之前已经求出来了，以此类推，直到k-n==1次结束。自己细想下就能明白的。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
    int dp[20][20],x[20];
    int v[]={0,8,10,6,3,7,2}; ///为便于读者阅读，初始化
    int w[]={0,4,6,2,2,5,1};
    int n=6,c=12;

    memset(dp,0,sizeof(dp)); ///小提醒：只能赋0，或-1
    for(int i=1;i<=n;i++)  ///从第1个到第i个物品中挑选出总重量不超过j的物品时总价值的最大值
    {
        for(int j=1;j<=c;j++)
        {
                ///此句与01背包中dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
                ///有区别哦，注意比较理解
                if(j<w[i]) dp[i-1][j];
               else  dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);

        }
    }
    printf("%d\n",dp[n][c]); ///总价值
   return 0;

}