USACO备考冲刺必刷题 | P2871 Charm Bracelet

学习C++从娃娃抓起！记录下USACO（美国信息学奥赛）备考学习过程中的题目，记录每一个瞬间。

附上汇总贴：USACO备考冲刺必刷题 | 汇总-CSDN博客

【题目描述】

有?N?件物品和一个容量为?M?的背包。第?i?件物品的重量是?Wi，价值是?Di。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

【输入】

第一行：物品个数?N?和背包大小?M。

第二行至第?N+1 行：第?i?个物品的重量?Wi?和价值?Di。

【输出】

输出一行最大价值。

【输入样例】

4 6
1 4
2 6
3 12
2 7

【输出样例】

23

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int n, m, w[4000], d[4000], dp[12890];
int main()
{
    cin >> n >> m;  // 输入n和m
    for (int i=1; i<=n; i++) {  // 输入n件无皮的重量和价值
        cin >> w[i] >> d[i];
    }   
    for (int i=1; i<=n; i++) {  // 01背包的模板（滚动数组版）
        for (int j=m; j>=w[i]; j--) {
            dp[j] = max(dp[j], dp[j-w[i]]+d[i]);
        }
    }
    cout << dp[m] << endl;  // 输出dp[m]
    return 0;
}

【运行结果】

4 6
1 4
2 6
3 12
2 7
23