完全背包

完全背包

原题链接

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

• 无优化版本

    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][j-k*v[i]]+k*w[i]);
    
    cout<<dp[n][m]<<endl;

• 优化时间复杂度

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

• 滚动数组优化

每种物品有无穷件

首先区别与01背包，因为物品有无穷件所以放第i件时转移到的是dp[i][x-w[i]]+c[i],在i-1时刻其存储的意义也是dp[x]记录的是前i-1个物品在容量是x时的最大值

所以x递增遍历的原因：因为放放第i件时转移到的是dp[i][x-w[i]]+c[i]，对应与dp[x-v[i]]+w[i],它表示的是前i个物品在容量是x-v[i]时的最大值，所以需要正序遍历

#include <iostream>
#include <algorithm>

using namespace std;

const int N=1010;

int n,m;
int dp[N];
int v[N],w[N];

int main()
{
    scanf("%d%d",&n,&m);
    
    for(int i=1;i<=n;i++)
        scanf("%d%d",&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]);//此时顺序枚举i，所以算的是第i时刻的dp值
    
    cout<<dp[m]<<endl;
    return 0;
}