头像

PureJoy


访客:30

离线:8天前



PureJoy
8天前

背包九讲中的多重背包1,为什么先枚举物品(k)再枚举背包容量(j)会出错?

代码:

#include<iostream>
using namespace std;
long long dp[100005];
int main()
{
    int m,n,v,w,t;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v>>w>>t;
        for(int k=1;k<=t;k++)
            for(int j=m;j>=k*v;j--)
                dp[j]=max(dp[j],dp[j-v*k]+w*k);
    }
    cout<<dp[m];
    return 0;
}