前言
动态规划——01背包的一些习题，包含如下题目：
⭐️ P1048 采药
⭐️ P2871 [USACO07DEC]Charm Bracelet S
⭐️ P1049 装箱问题
⭐️ P1060 开心的金明
⭐️ P1164 小A点菜
⭐️ P1510 精卫填海
⭐️ P2639 [USACO09OCT]Bessie’s Weight Problem G
⭐️ P2925 [USACO08DEC]Hay For Sale S
⭐️ P1926 小书童——刷题大军
⭐️ P1802 5倍经验日
⭐️ P1734 最大约数和
⭐️ P2392 kkksc03考前临时抱佛脚
刷题记录，不提供代码解释，01背包的讲解博客见：01背包问题及二维费用背包问题
P1048 [NOIP2005 普及组] 采药
本博客给出本题截图：
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1010; int f[N]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= m; i ++ ) { int v, w; cin >> v >> w; for (int j = n; j >= v; j -- ) f[j] = max(f[j], f[j - v] + w); } cout << f[n] << endl; return 0; }
P2871 [USACO07DEC]Charm Bracelet S
本题链接：P2871 [USACO07DEC]Charm Bracelet S
本博客给出本题截图：
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 12890; int f[N]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i ++ ) { int v, w; cin >> v >> w; for (int j = m; j >= v; j -- ) f[j] = max(f[j], f[j - v] + w); } cout << f[m] << endl; return 0; }
P1049 [NOIP2001 普及组] 装箱问题
本题链接：P1049 [NOIP2001 普及组] 装箱问题
本博客给出本题截图：
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 20010; int f[N]; int main() { int m, n; cin >> m >> n; for (int i = 1; i <= n; i ++ ) { int v; cin >> v; for (int j = m; j >= v; j -- ) f[j] = max(f[j], f[j - v] + v); } cout << m - f[m] << endl; return 0; }
P1060 [NOIP2006 普及组] 开心的金明
本题链接：P1060 [NOIP2006 普及组] 开心的金明
本博客给出本题截图：
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 30010; int f[N]; int main() { int n, m; cin >> m >> n; for (int i = 1; i <= n; i ++ ) { int v, p; cin >> v >> p; int w = v * p; for (int j = m; j >= v; j -- ) f[j] = max(f[j], f[j - v] + w); } cout << f[m] << endl; return 0; }
