题目描述
将每个背包的模板套进去就ok,耗时300多
include[HTML_REMOVED]
using namespace std;
const int N=1010;
int f[N];
int n,m;
int main(){
cin>>n>>m;
for(int i=0;i[HTML_REMOVED]>v>>w>>s;
if(s==-1){
for(int j=m;j>=v;j–)
f[j]=max(f[j],f[j-v]+w);
}
else if(s==0)
for(int j=v;j<=m;j++)
f[j]=max(f[j],f[j-v]+w);
else{
vector[HTML_REMOVED]t;
for(int k=1;k<=s;k=2)
{
t.push_back(k);
s-=k;
}
if(s)t.push_back(s);
for(int i=0;i[HTML_REMOVED]=t[i]v;j–)
f[j]=max(f[j],f[j-t[i]v]+t[i]w);
}
}
cout<<f[m];
return 0;
}
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla