本文最后更新于 44 天前，其中的信息可能已经有所发展或是发生改变。
例题
假设你是一个高中生，你有一个背包，书包的容量是10公斤。现在你有三种不同的参考书需要带去学校，每种书都有不同的重量和价值，以及每种书你有几本：
- 数学书：每本重量2公斤，价值5元，你有3本。
- 语文书：每本重量3公斤，价值10元，你有2本。
- 英语书：每本重量2.5公斤，价值7元，你有2本。
你的任务是选择一些书放入书包，使得书包内的书总价值最大，同时不超过书包的容量。
个人思路
朴素算法：多用一层for循环嵌套在中间根据存储在数组的关于物品的数量来确定循环次数即就是在0-1背包问题中根据物品数量拓展与展开。
代码展示
#include <iostream>
#include <vector>
using namespace std;
// 物品的结构体，包含重量、价值和数量
struct Item {
int weight;
int value;
int quantity;
};
// 动态规划解决多重背包问题
int knapsack(int W, vector<Item>& items) {
// 创建一个一维数组dp，用于存储最大价值
vector<int> dp(W + 1, 0);
// 遍历所有物品
for (int i = 0; i < items.size(); ++i) {
// 对于每种物品，拆分为若干个0-1背包问题中的物品
for (int k = 1; k <= items[i].quantity; ++k) {
// 从背包容量大到小遍历，避免重复放入同一个物品
for (int w = W; w >= items[i].weight; --w) {
// 如果当前物品可以放入背包，则更新dp数组
dp[w] = max(dp[w], dp[w - items[i].weight] + items[i].value
}
}
}
}
// 返回最大价值
return dp[W];
}
int main() {
// 背包的最大容量
int W = 10;
// 物品列表，包含每种物品的重量、价值和数量
vector<Item> items = {
{2, 5, 3}, // 数学书
{3, 10, 2}, // 语文书
{2.5, 7, 2} // 英语书
};
// 计算并输出最大价值
cout << "The maximum value of items that can be carried: " << knapsack(W, items) << endl;
return 0;
}
细节注释
此处直接采用滚动规划来优化空间复杂度。（易错点：容易在最内层for循环中加入if-else——然后用其中数量k去计算是否符合，此处完全没有必要）
优化
二进制优化：（以后填）