朴素版 现在 TLE
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i++)
for(int j = 0; j <= m; j++)
for(int k = 0; k*v[i] <= j; k++)
f[i][j] = max(f[i][j], f[i-1][j - v[i] * k] + w[i] *k);
cout << f[n][m] << endl;
return 0;
}
优化二维 类比 01 背包问题可以优化成 1 维
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i++)
for(int j = 0; j <= m; j++)
{
f[i][j] = f[i-1][j];
if(j >= v[i]) f[i][j] = max(f[i][j], f[i][j-v[i]] + w[i]);
}
cout << f[n][m] << endl;
return 0;
}
优化一维
这里的内层循环不用使用倒序
因为 f[j - v[i]] + w[i] 用的是 第 i 层的 f[j - v[i]]
f[j] 是 i- 1 层的 因为 i 层的 j 还没有更新,所以存的还是 i - 1 层的 j
而 i 层的 j - v[i] 在本层更新
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i++)
for(int j = v[i]; j <= m; j++)
f[j] = max(f[j], f[j - v[i]] + w[i]);
// f[i-1][j]
// f[i][j-v[i]] +w[i]
cout << f[m] << endl;
return 0;
}