01背包

题目描述

有N件物品和一个容量为V的背包。第i件物品的重量是w[i],价值是c[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量,且价值总和最大。

输入描述

第一行为N(1N5000)(1≤N≤5000),V(1V5000)(1≤V≤5000)

下面N行,第i行描述第i个物品的w[i](1w[i]103)(1≤w[i]≤10^3),c[i](1c[i]103)(1≤c[i]≤10^3),用一个空格分隔。

输出描述

输出只有一个数,最大总价值。

测试样例

输入

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];
}