2048: 多重背包

将n个物品注意拆分转化为01背包问题

#include<iostream>

using namespace std;

int dp[10000];

int w[105],v[105],c[1050];

int n,m;

int main()

{

    cin>>n>>m;

    for(int i=1;i<=n;i++){

        cin>>w[i]>>v[i]>>c[i];

    }

    for(int i=1;i<=n;i++){

        for(int j=m;j>=0;j--){

            for(int k=1;k<=c[i];k++){

                if(j>=w[i]*k){

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

                }

            }

        }

    }

    cout<<dp[m]<<endl;

    return 0;

}