1、二维数组构建01背包（不推荐）
例题
题解
#include <iostream>
using namespace std;
int packet[101][1010] = { 0 }; //packet[i][j] 为剩余 i 株草药、j 段时间时，可以获得的最大价值
int t[101] = { 0 }; //时间
int w[101] = { 0 }; //价值
int main() {
int T, M;
cin >> T >> M;
int a, b;
for (int i = 1; i <= M; i++) {
cin >> a >> b;
t[i] = a; //存入一株草药的时间
w[i] = b; //存入一株草药的价值
}
for (int n = 1; n <= M; n++) { //构建背包，先从只有 1 株草药开始
for (int ti = 1; ti <= T; ti++) { //从剩余时间为 1 时开始
if (t[n] > ti) { //采取的第 n 株草药所需时间大于当前剩余时间
packet[n][ti] = packet[n-1][ti];
}
else { //时间充裕，可以采取第 n 株草药
int value1 = packet[n-1][ti-t[n]] + w[n]; //如果采它，则获得价值为 value1
int value2 = packet[n-1][ti]; //如果不采，则获得价值为 value2
if (value1 > value2) { //通过比较两者大小来决定剩余 n 株草药、t 段时间时可获得的最大价值
packet[n][ti] = value1;
}
else {
packet[n][ti] = value2;
}
}
}
}
cout << packet[M][T] ; //输出 packet[M][T] 即可得到本题答案
return 0;
}
2、一维数组构建01背包
例题
题目翻译
Bessie 去了商场的珠宝店，发现了一个手链。 当然，她想用 N (1 ≤ N ≤ 3,402) 个可用护符中最好的护符来填充它。 提供的列表中的每个魅力 i 都有一个权重 Wi (1 ≤ Wi ≤ 400)，一个“合意性”因子 Di (1 ≤ Di ≤ 100)，并且最多可以使用一次。 Bessie 只能支撑重量不超过 M（1 ≤ M ≤ 12,880）的吊饰手链。
将权重限制作为约束条件以及魅力列表及其权重和合意性评级，推导出最大可能的评级总和。
输入
* 第 1 行：两个空格分隔的整数：N 和 M
* 第 2..N+1 行：第 i+1 行用两个空格分隔的整数描述魅力 i：Wi 和 Di
输出
* 第 1 行：单个整数，是在给定权重限制的情况下可以实现的魅力愿望的最大总和
样本输入
4 6
1 4
2 6
3 12
2 7
样本输出
23
题解
由于本题数据较大，用二维数组会造成内存溢出，故使用一维数组
同时也推荐解题使用一维数组，二维数组只是便于理解，而一维数组相当于二维数组的某一行
本题状态转移方程为：
dp[j] = max(dp[j], dp[j - m[i]] + w[i])
#include <iostream>
#include <algorithm>
using namespace std;
int m[3403] = { 0 }, w[3403] = { 0 }; //m 为重量，w 为价值（魅力值）
int dp[12881] = { 0 }; //数组 dp[i] 记录了剩余 i 重量时可以获得的最大魅力值
int main() {
int N, M; //N 个护符，M 的支撑重量
cin >> N >> M;
int a, b;
for (int i = 1; i <= N; i++) { //录入各组数据
cin >> a >> b;
m[i] = a; w[i] = b;
}
for (int i = 1; i <= N; i++) { //从只有 1 个护符开始，相当于从二维数组的第一行开始
for (int j = M; j >= m[i]; j--) { //直接从剩余 M 重量开始，与二维数组不同
dp[j] = max(dp[j], dp[j - m[i]] + w[i]);
}
}
cout << dp[M];
return 0;
}
3、多重背包
例题
题解
本题属于二重完全背包，需构建二维数组，实质上在处理上就是比一维数组多了一个 for 循环
本题状态转移方程为：
dp[h][j] = max(dp[h][j], dp[h - 1][j - w[i]] + v[i])
#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int dp[110][110]; //刷 i 只怪，剩余 j 个忍耐值可获得的最大经验
int v[110], w[110]; //v 价值，w 重量(消耗的忍耐度)
int main() {
int n, m, k, s; //n 经验值，m 忍耐度，k 种怪，s 最多杀怪数
while (cin >> n >> m >> k >> s) {
for (int i = 1; i <= k; i++) {
scanf("%d%d", &v[i], &w[i]);
}
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= k; i++) { //从只有 1 种怪开始
for (int j = w[i]; j <= m; j++) { //从可以有足够忍耐度打怪开始
for (int h = 1; h <= s; h++) { //从杀 1 只怪开始
dp[h][j] = max(dp[h][j], dp[h - 1][j - w[i]] + v[i]);
//杀 h 只怪，剩余 j 个忍耐值可获得的最大经验
}
}
}
if (dp[s][m] >= n) { //当存在可以升级的打怪方式时
for (int i = 1; i <= m; i++) {
if (dp[s][i] >= n) { //第一个数据即为所求数据
printf("%d\n", m - i); //输出 m - i 即可得到本题答案
break;
}
}
}
else
printf("-1\n");
}
return 0;
}