直入正题:
01 背包只有 拿 和 不拿 两种情况,那么就列出动态转移方程:
$$f_(i,j) = max (f_(i-1,j), f_(i-1,j-v_i)+w_i$$
优化空间复杂度后:
$$f_j = max (f_j, f_(j-v_i)+w_i$$
那么最后 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];
}