题目描述

完全背包问题（每个物品可以选多次）

选法：
（1）从1~i个物品中选，不选第i个物品，f[i-1][j]
（2）从1~i个物品中选，可选多个第i个物品，
f[i-1][j-v],f[i-1][j-2v]…

所以f[i][j]=max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w…)
用j-v代替上面的j得
f[i][j-v]=max(f[i-1][j-2v]+w,f[i-1][j-3v]+w…)总式子比上面少w

所以f[i][j]=max(f[i-1][j],f[i],[j-v]+w)

算法1

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int V[N],W[N];
int f[N][N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>V[i]>>W[i];

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            f[i][j]=f[i-1][j];  //从1~i中选，不选第i个物品
            if(j>=V[i])
            {
                f[i][j]=max(f[i-1][j],f[i][j-V[i]]+W[i]);   
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

算法2

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int V[N],W[N];
int f[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>V[i]>>W[i];

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            f[j]=f[j];
            if(j>=V[i])
            {
                f[j]=max(f[j],f[j-V[i]]+W[i]);
            }
        }
    }
    cout<<f[m]<<endl;
    return 0;
}