✅作者简介：人工智能专业本科在读，喜欢计算机与编程，写博客记录自己的学习历程。
?个人主页：小嗷犬的个人主页
?个人网站：小嗷犬的技术小站
?个人信条：为天地立心，为生民立命，为往圣继绝学，为万世开太平。
本文目录
- 背包问题
- 0-1 背包问题
- 完全背包问题
- 多重背包问题
背包问题
背包问题是数学建模中的一个经典问题，其目的是在给定的背包容量下，选择一组物品，使得物品的价值最大化。在实际生活中，背包问题可以用于物流运输、物资调度等领域。
常见的背包问题有 0-1 背包问题、完全背包问题、多重背包问题等。
0-1 背包问题
0-1 背包问题是最基本的背包问题，即每个物品只能选择 0 个或 1 个。
通常使用动态规划的方法求解 0-1 背包问题。
例
有 4 件物品，重量分别为 2、2、6、5，价值分别为 6、3、5、4，背包容量为 10，求背包中物品的最大价值。
解
-
将原问题分解为子问题：将问题分解为前
i件物品放入容量为j的背包中所能获得的最大价值。 -
确定状态：
i件物品放入容量为j的背包中所能获得的最大价值。 -
确定一些初始状态（边界状态）的值：当
i = 0时，j件物品放入容量为j的背包中所能获得的最大价值为 0；当j = 0时，i件物品放入容量为j的背包中所能获得的最大价值为 0。 -
确定状态转移方程：当
i件物品放入容量为j的背包中所能获得的最大价值为max{f(i-1,j),f(i-1,j-w(i))+v(i)}，其中w(i)为第i件物品的重量，v(i)为第i件物品的价值。
可得出以下代码：
function [f] = knapsack(w,v,c)
% w: 物品重量
% v: 物品价值
% c: 背包容量
n = length(w);
f = zeros(n+1,c+1); % f(i,j)表示前i-1件物品放入容量为j-1的背包中所能获得的最大价值
for i = 2:n+1
for j = 2:c+1
if w(i-1) < j
f(i,j) = max(f(i-1,j),f(i-1,j-w(i-1))+v(i-1));
else
f(i,j) = f(i-1,j);
end
end
end
f = f(n+1,c+1);
end
调用函数求解：
w = [2,2,6,5];
v = [6,3,5,4];
c = 10;
f = knapsack(w,v,c)
结果：
f = 14
完全背包问题
完全背包问题是背包问题的一种，即每种物品可以选择任意个。
我们可以将其转化为 0-1 背包问题，即将每种物品拆分为若干个物品，每个物品的重量和价值都相同。
例
有 4 种物品，重量分别为 2、2、6、5，价值分别为 6、3、5、4，背包容量为 20，求背包中物品的最大价值。
解
将每种物品拆分为 c/w 个物品，并求解：
w = [2,2,6,5];
v = [6,3,5,4];
c = 20;
num = floor(c./w);
w = repelem(w,num);
v = repelem(v,num);
f = knapsack(w,v,c)
结果：
f = 60
多重背包问题
多重背包问题是背包问题的一种，即每种物品可以选择有限个。
我们可以将其转化为 0-1 背包问题，即将每种物品拆分为若干个物品。
例
有 4 种物品，重量分别为 2、2、6、5，价值分别为 6、3、5、4，每种物品的数量分别为 3、1、2、1，背包容量为 20，求背包中物品的最大价值。
解
将每种物品拆分为 num(i) 个物品，并求解：文章来源：https://uudwc.com/A/AV8V
w = [2,2,6,5];
v = [6,3,5,4];
num = [3,1,2,1];
c = 20;
w = repelem(w,num);
v = repelem(v,num);
f = knapsack(w,v,c)
结果：文章来源地址https://uudwc.com/A/AV8V
f = 31
