完全背包实际上与01背包没什么区别，我们知道01背包的问题是这么描述的：

有 N件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

而这跟完全背包不同的地方在于完全背包的每种物品有无限个，01背包每种物品只有一个。

分析

那我们在考虑第i个物品时，除了要考虑该物品取不取，还要考虑该物品取多少个；

我们可以在01背包的基础上，再枚举该物品要取多少个；

for(int i=1;i<=n;i++)
{
    for(int j=0;j<=m;j++)
    {
        for(int k=0;k*v[i]<=j;k++)//对物品的数量进行枚举
        {
             dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]*k]+w[i]*k);
        }
    }
}

你可能发现了，为什么是dp[i][j]而不是像01背包一样是dp[i-1][j]?

其实真正的状态转移方程是这样的：

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

当k=0时，dp[i][j]=max(dp[i-1][j],dp[i-1][j]),实际上是一样的，所以dp[i-1][j-v[i]*k]+w[i]*k就已经包括了

dp[i-1][j]；又因为有这已成循环的存在，max里面的dp[i][j]也是必须要有的，此时的dp[i][j]记录的是k-1个i物品的总价值；

但如果这么写，时间复杂度大概为O(nm²),数据稍微强一点，肯定过不去；

优化

我们把方程展开之后发现：

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

比对之后我们可以发现：

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

我们就去掉了一层循环

for(int i=1;i<=n;i++)
{
    for(int j=0;j<=m;j++)
    {
         dp[i][j]=dp[i-1][j];
         if(v[i]<=j)dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
    }
}

我们同样可以通过滚动数组将其变成一维的，最终代码就成了这样：

for(int i=1;i<=n;i++)
{
    for(int j=v[i];j<=m;j++)
    {
        dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    }
}