题目描述
有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
输入描述
第一行为N，V。
下面N行，第i行描述第i个物品的w[i]，c[i]，用一个空格分隔。
输出描述
输出只有一个数，最大总价值。
测试样例
输入
10 9
7 1
8 10
7 10
7 7
7 6
3 7
4 1
3 3
9 1
1 4
输出
14
#include <bits/stdc++.h>
using namespace std;
int dp[5005], w[5005], v[5005], n, tw, tv, bv;
int main() {
cin >> n >> bv;
for (int i = 1; i <= n; ++i)
scanf(" %d%d", &tw, &tv), w[i] = tw, v[i] = tv;
for (int i = 1; i <= n; ++i)
for (int j = bv; j >= 1; --j)
if (j - w[i] >= 0)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
cout << dp[bv];
}