题目描述
blablabla
样例
blablabla
合并后为
f[i][j]=max(f[i-1][j],f[i][j-v]+w-f[i-1][j-(s+1)v]+sw)
其实是不能合并的,因为不是完全相同的两个整体,合并后max不一样
不能像完全背包一样优化
算法1
(暴力枚举) $O(n^2)$
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int m,n;
int w[N],v[N],s[N];
int f[N][N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>v[i]>>w[i]>>s[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
}
cout<<f[n][m]<<endl;
return 0;
}
#### 时间复杂度
#### 参考文献
#### C++ 代码
blablabla
----------
### 算法2
##### (暴力枚举) $O(n^2)$
blablabla
#### 时间复杂度
#### 参考文献
#### C++ 代码
blablabla
```