直入正题:
01 背包只有 拿 和 不拿 两种情况,那么就列出动态转移方程:
f(i,j)=max(f(i−1,j),f(i−1,j−vi)+wi
优化空间复杂度后:
fj=max(fj,f(j−vi)+wi
那么最后 code:
#include <bits/stdc++.h>
using namespace std;
const int n = 1e3 + 5;
int N, V;
int v[n], w[n], f[n];
int main() {
cin >> N >> V;//按照题目定义>_<
for (int i=1; i<=N; i++) cin >> v[i] >> w[i];
for (int i=1; i<=N; i++)
for (int j=V; j>=v[i]; j--)
f[j] = max (f[j], f[j-v[i]] + w[i]);//动态转移方程
cout << f[V];
}