AcWing 1. 多重背包问题 I
原题链接
简单
作者:
赵枫灵
,
2019-11-08 16:59:38
,
所有人可见
,
阅读 1102
原题链接
https://www.acwing.com/problem/content/description/4/
样例
IN
4 5
1 2 3
2 4 1
3 4 3
4 5 2
OUT
10
解释
这道题我们可以把数目不唯一的一个物体看成是数目均为一的不同物体,但价值、所占空间一样,这样就改成了01背包模板题格式。
数据范围的话,因为n<=100,s[i]<=100,所以开个10005的数组就可以了。
(萌新第 一次写题解,不好请见谅)
C++ 代码
//如下
#include[HTML_REMOVED]
using namespace std;
const int M=10005;
int n,m,i,j,k,v[M],w[M],s[M],f[M],t;
int main(){
cin>>n>>m;
for(i=1;i<=n;i++)
{
cin>>v[i]>>w[i]>>s[i];
}
k=n+1;
for(i=1;i<=n;i++)
{
t=s[i];
while(t>1){
w[k]=w[i];
v[k]=v[i];
k++;
t–;
}
}
for(i=1;i<=k;i++)
{
for(j=m;j>=v[i];j–)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m];
return 0;
}