题解：洛谷 P2871 [USACO07DEC] Charm Bracelet S

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P2871 [USACO07DEC] Charm Bracelet S – 洛谷

【题目描述】

有

N

N

N 件物品和一个容量为

M

M

M 的背包。第

i

i

i 件物品的重量是

W

i

W_i

Wi​，价值是

D

i

D_i

Di​。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

【输入】

第一行：物品个数

N

N

N 和背包大小

M

M

M。

第二行至第

N

+

1

N+1

N+1 行：第

i

i

i 个物品的重量

W

i

W_i

Wi​ 和价值

D

i

D_i

Di​。

【输出】

输出一行最大价值。

【输入样例】

4 6
1 4
2 6
3 12
2 7

【输出样例】

23

【核心思想】

【解题思路】

【算法标签】

#普及- #01背包

【代码详解】

#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