和01背包一样,不过遍历c遍而已
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int dp[1005];
int main()
{
int n,m,a,b,c;
cin >> n >> m;
for(int i=0;i<n;++i){
cin >> a >> b >> c;
for(int i=1;i<=c;++i){ //c遍 01背包就可以了
for(int j=m;j>=a*i;--j){
dp[j]=max(dp[j],dp[j-a]+b);
}
}
}
cout << dp[m];
return 0;
}
还有一种非二进制、非单调队列的优化代码,完全可以通过多重背包问题II和III,
我放在这里了 链接 (https://www.acwing.com/solution/acwing/content/4940/)