使用adagio包解决背包问题

时间:2022-03-13 12:54:14

背包问题(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

使用adagio包解决背包问题

见上图,有一个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包解决背包问题

则,利用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

使用adagio包解决背包问题

反馈与建议