背包问题(Knapsack problem)
背包问题(Knapsack problem)是一种组合优化的多项式复杂程度的非确定性问题（NP问题）。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V。它是在1978年由Merkel和Hellman提出的。
解决背包问题可以通过一系列的经典算法，比如动态规划法、贪心法、分支界限法和遗传算法等方法解决。
问题描述
有n个物品，编号1,2,3,...,n，其中第 i 个物品重量为\(w_{i}\)、价值\(v_{i}\) ，有一个容量为W的背包。对于每个物品，要么取走要么不取走，每个物品只能取一次。用数学表达式表示为：
\[max \sum_{i=1}^{n}v_{i}x_{i}
\]
\]
\[s.t. \sum_{i=1}^{n}w_{i}x_{i}\leqslant W , x_{i}\in \left \{0,1 \right \}
\]
\]
总而言之，在容量允许范围内，如何选择物品，可以得到最大的价值,就是一个背包问题。
案例1
见上图，有一个15kg的背包和5种不同物品，寻找一种方法使装入背包里的物品得到最大的价值。通过adagio包，可以很轻松地解决这个问题。
library(adagio) #载入adagio包
p <- c(2, 1, 10, 2, 4) #价值
w <- c(2, 1, 4, 1, 12) #重量
cap <- 15 #容量
knapsack(w, p, cap) #求解
优化结果：
$capacity
[1] 8
$profit
[1] 15
$indices
[1] 1 2 3 4
案例2
有五根长度分别为120、137、220、420、480cm的木头，想将其分割成19cm四根、 79cm三根、103cm三根、135cm四根、160cm一根。用于打造一个组合阶梯。
则，利用adagio包解决此问题的方法为：
library(adagio)
planks_we_have <- c(120, 137, 220, 420, 480)
planks_we_want <- c(19, 19, 19, 19, 79, 79, 79, 103, 103,
103, 135, 135, 135, 135, 160)
solution <- mknapsack(planks_we_want, planks_we_want + 1, planks_we_have)
# +1的意思是每次切割后损失1cm。
solution$ksack
优化结果：
$ksack
[1] 1 4 4 1 1 3 4 5 5 5 5 4 2 3 4
反馈与建议
- 作者：ShangFR
- 邮箱：shangfr@foxmail.com