我的现实生活中的随身背包的背包问题算法
背包问题
布置
数据结构
贪婪算法
动态规划
哪种方法更好？
背包问题
我居无定所，只带一个随身行李箱。这意味着我所有家当的总重量必须符合航空公司对随身行李的重量限制——通常是10公斤。不过，在一些规模较小的航空公司，这个限制会降到7公斤。有时，为了适应较低的重量限制，我不得不放弃携带某些东西。
作为一项实践练习，决定留下哪些东西（或者彻底丢弃哪些东西）需要我把所有物品都摆出来，然后从中挑选出要保留的。这个决定基于物品对我的实用性（它的价值）和它的重量。
这就是我的所有东西，还有我的 Minaal 随身行李包。
作为一名程序员，我知道像这样的决策可以由计算机更高效地完成。事实上，这种情况如此普遍，以至于许多人都会将其视为经典的打包问题或背包问题。我该如何告诉计算机，在背包重量不超过 7 公斤的前提下，尽可能多地装下重要的物品呢？答案是：用算法！太棒了！
我将讨论解决背包问题的两种常见方法：一种称为贪婪算法，另一种称为动态规划（稍微难一些，但更好、更快、更强……）。
让我们开始吧。
布置
我将数据整理成一个包含三列的 CSV 文件：物品名称（字符串）、物品价值（整数）和物品重量（克，整数）。总共有 40 件物品。我通过对每件物品进行 40 到 1 的排序来表示其价值，40 代表最重要，1 则代表“我为什么还要留着它？”（如果你从未列出所有物品并按实用性排序，我强烈建议你尝试一下。这会是一个非常有启发性的练习。）
所有物品及袋子的总重量： 9003克
包装重量： 1415克
航空公司限重： 7000克
我最多可以打包重量为： 5585克
物品总价值： 820
挑战：在限额允许的范围内打包尽可能多的物品，同时最大化总价值。
数据结构
读取文件
在开始思考如何解决背包问题之前，我们必须先解决数据的读取和存储问题。幸运的是，Go 标准库的io/ioutil包让第一步变得非常简单。
package main
import (
"fmt"
"io/ioutil"
)
func check(e error) {
if e != nil {
panic(e)
}
}
func readItems(path string) {
dat, err := ioutil.ReadFile(path)
check(err)
fmt.Print(string(dat))
}
该ReadFile()函数接收一个文件路径作为参数，并返回文件内容以及一个错误信息（nil如果调用成功）。因此，我们也创建了一个check()函数来处理可能返回的任何错误。在实际应用中，我们可能需要更复杂的处理方式panic，但目前这并不重要。
创建结构体
现在我们已经有了数据，应该对它进行一些处理。由于我们处理的是真实物品和一个真实的包，让我们创建一些类型来表示它们，以便更容易理解我们的程序。struct在 Go 语言中，A 是字段的类型化集合。以下是我们的两个类型：
type item struct {
name string
worth, weight int
}
type bag struct {
bagWeight, currItemsWeight, maxItemsWeight, totalWeight int
items []item
}
使用描述性强的字段名很有帮助。可以看到，结构体的设置正如我们描述的那样，它们代表了相应的对象。一个结构体item包含一个name字符串类型的字段，以及一个worth整数weight类型的字段。结构体bag包含多个类型为 `thingamabobbers`int的字段，分别代表其属性，并且还可以存储`thingamabobbers` 类型的切片。itemsitem
解析和存储我们的数据
有很多功能全面的 Go 包可以用来解析我们的 CSV 数据……但这有什么乐趣可言呢？让我们回归基本，使用字符串分割和 for 循环。以下是更新后的readItems()函数：
func readItems(path string) []item {
dat, err := ioutil.ReadFile(path)
check(err)
lines := strings.Split(string(dat), "\n")
itemList := make([]item, 0)
for i, v := range lines {
if i == 0 {
continue
}
s := strings.Split(v, ",")
newItemWorth, _ := strconv.Atoi(s[1])
newItemWeight, _ := strconv.Atoi(s[2])
newItem := item{name: s[0], worth: newItemWorth, weight: newItemWeight}
itemList = append(itemList, newItem)
}
return itemList
}
我们使用换行符strings.Split来分割dat文本。然后创建一个空的元素itemList来存放这些元素。
在我们的 for 循环中，我们跳过 CSV 文件的第一行（标题行），然后遍历每一行。我们使用strconv.Atoi`A` 到 `i` 的函数将每个项目的金额和重量值转换为整数。然后，我们创建一个newItem包含这些字段值的数组，并将其附加到 `A` 到 `B` 的数组中itemList。最后，我们返回 `B`到 `B` 的数组itemList。
以下是我们目前的配置情况：
package main
import (
"io/ioutil"
"strconv"
"strings"
)
type item struct {
name string
worth, weight int
}
type bag struct {
bagWeight, currItemsWeight, maxItemsWeight, totalWeight, totalWorth int
items []item
}
func check(e error) {
if e != nil {
panic(e)
}
}
func readItems(path string) []item {
dat, err := ioutil.ReadFile(path)
check(err)
lines := strings.Split(string(dat), "\n")
itemList := make([]item, 0)
for i, v := range lines {
if i == 0 {
continue // skip the headers on the first line
}
s := strings.Split(v, ",")
newItemWorth, _ := strconv.Atoi(s[1])
newItemWeight, _ := strconv.Atoi(s[2])
newItem := item{name: s[0], worth: newItemWorth, weight: newItemWeight}
itemList = append(itemList, newItem)
}
return itemList
}
现在我们已经搭建好了数据结构，让我们开始第一种方法的打包（🥁）。
贪婪算法
贪心算法是解决背包问题最直接的方法，因为它只需遍历一次就能找到一个最终解。在问题的每个阶段，贪心算法都会选择局部最优解，也就是当前看来最合适的选项。它不会在遍历数据集的过程中修改之前的选择。
构建我们的贪婪算法
我们将使用以下算法来解决背包问题：
- 按价值降序排列物品。
- 先从价值最高的物品开始。把物品放进袋子里，直到装不下清单上的下一件物品为止。
- 尽量用列表中下一个可以放进去的物品填满剩余的空间。
如果你读过我那篇关于解决问题和制作西班牙海鲜饭的文章，你就会知道我总是先弄清楚下一个最重要的问题是什么。在这个例子中，我们需要弄清楚如何完成三个主要操作：
- 按价值排序。
- 将一件物品放入袋中。
- 检查一下袋子是否满了。
第一个问题只需查阅文档即可解决。以下是 Go 语言中对切片进行排序的方法：
sort.Slice(is, func(i, j int) bool {
return is[i].worth > is[j].worth
})
该sort.Slice()函数根据我们提供的最小值函数对商品进行排序。在本例中，它会将价值最高的商品排在价值最低的商品之前。
鉴于我们不希望把不合适的物品放进袋子里，我们将反向完成最后两项任务。首先，我们检查物品是否合适。如果合适，就把它放进袋子里。
func (b *bag) addItem(i item) error {
if b.currItemsWeight+i.weight <= b.maxItemsWeight {
b.currItemsWeight += i.weight
b.items = append(b.items, i)
return nil
}
return errors.New("could not fit item")
}
注意*我们第一行中的 `@Pointer`。这表明它bag是一个指针接收器（而不是值接收器）。如果您是 Go 新手，这个概念可能会有点令人困惑。以下几点或许能帮助您判断何时使用值接收器，何时使用指针接收器。就我们的addItem()函数而言，这种情况适用：
如果该方法需要修改接收器，则接收器必须是指针。
我们使用指针接收器来告诉函数，我们要操作的是这个特定的包，而不是一个新的包。这一点很重要，因为如果没有它，每个物品都会被自动放入一个新创建的包里！像这样的小细节，就能决定你的代码是能正常运行，还是让你熬夜到凌晨四点，一边狂灌红牛一边自言自语。（即使你的代码运行不正常，也要按时睡觉——你会感谢我的。）
现在我们已经有了所有组件，让我们来组装贪婪算法：
func greedy(is []item, b bag) {
sort.Slice(is, func(i, j int) bool {
return is[i].worth > is[j].worth
})
for i := range is {
b.addItem(is[i])
}
b.totalWeight = b.bagWeight + b.currItemsWeight
for _, v := range b.items {
b.totalWorth += v.worth
}
}
然后，在我们的main()函数中，我们将创建数据包，读取数据，并调用贪婪算法。以下是设置完毕、准备就绪后的样子：
func main() {
minaal := bag{bagWeight: 1415, currItemsWeight: 0, maxItemsWeight: 5585}
itemList := readItems("objects.csv")
greedy(itemList, minaal)
}
贪婪算法结果
那么，这个算法在高效打包行李以最大化其总价值方面表现如何呢？结果如下：
背包及物品总重量： 6987克
包装物品总价值： 716
以下是我们的贪婪算法选择的物品，按价值排序：
| 物品 | 值得 | 重量 |
|---|---|---|
| 联想 X1 Carbon（第五代） | 40 | 112 |
| 10条丁字裤 | 39 | 80 |
| 5 Under Armour 绑带 | 38 | 305 |
| 优衣库打底裤一条 | 37 | 185 |
| 2. Lululemon Cool Racerback | 36 | 174 |
| 迷你轰炸机旅行套装中的充电器和线缆 | 35 | 665 |
| 栖息处 | 34 | 170 |
| ThinkPad 紧凑型蓝牙键盘，带指点杆 | 33 | 460 |
| 希捷 Backup Plus Slim | 32 | 159 |
| 1条黑色牛仔短裤 | 31 | 197 |
| 2条耐克专业短裤 | 30 | 112 |
| 2条 Lululemon 短裤 | 29 | 184 |
| 伊莎贝拉 T 字带鳄鱼凉鞋 | 28 | 200 |
| 2 件 Under Armour HeatGear CoolSwitch 背心 | 27 | 138 |
| 5双黑色袜子 | 26 | 95 |
| 2双 Injinji 女士跑步轻薄隐形五趾袜 | 25 | 54 |
| 1件漂亮的背心 | 24 | 71 |
| 1 件轻薄弹力长袖衬衫（Gap Fit 款） | 23 | 147 |
| 优衣库超轻羽绒服 | 22 | 235 |
| Patagonia Torrentshell | 21 | 301 |
| 轻便美利奴羊毛头巾 | 20 | 50 |
| 1 小黑裙（H&M） | 19 | 174 |
| Field Notes 纯黑色点阵备忘录 | 18 | 68 |
| Innergie PocketCell USB-C 6000mAh 移动电源 | 17 | 14 |
| JBL Reflect Mini 蓝牙运动耳机 | 13 | 14 |
| Oakley Latch 太阳镜 | 11 | 30 |
| Petzl E+LITE 应急头灯 | 8 | 27 |
很明显，贪婪算法是一种快速找到可行解的直接方法。对于小数据集，它很可能接近最优解。该算法打包了总价值为 716 的物品（比最大可能值少 104 分），而袋子只剩下 13 克。
正如我们之前了解到的，贪婪算法并不会改进它返回的解。它只是简单地将下一个价值最高的物品添加到背包中。
让我们来看另一种解决背包问题的方法，这种方法可以得到最优解——在重量限制下，背包的总价值尽可能高。
动态规划
“动态规划”这个名称可能会有点误导性。它并非一种编程风格，正如其名称可能让你联想到的那样，而只是一种不同的编程方法。
动态规划与简单的贪心算法在几个关键方面有所不同。首先，动态规划的装袋方案会枚举整个解空间，即所有可能用于装袋的物品组合。贪心算法只能找到局部最优解，而动态规划算法则能够找到全局最优解。
其次，动态规划利用记忆化技术存储先前计算的结果，并在再次执行相同操作时返回缓存的结果。这使得它能够“记住”之前的组合。相比重新计算答案，这种方法耗时更短。
构建我们的动态规划算法
要使用动态规划找到打包行李的最佳方案，我们需要：
- 创建一个矩阵，表示所有物品子集（解空间），其中行代表物品，列代表袋子的剩余承重能力。
- 遍历矩阵，计算在背包容量的每个阶段，每种物品组合所能获得的价值。
- 检查已完成的矩阵，确定应向袋子中添加哪些物品，以使袋子的总价值最大化。
将我们的解决方案空间可视化将非常有帮助。以下是我们用代码构建的内容的示意图：
空无一物的背包多元宇宙。
在 Go 语言中，我们可以将这个矩阵创建为切片的切片。
matrix := make([][]int, numItems+1) // rows representing items
for i := range matrix {
matrix[i] = make([]int, capacity+1) // columns representing grams of weight
}
我们对行和列进行了填充，1以便索引与项目和重量编号相匹配。
现在我们已经创建了矩阵，接下来我们将通过遍历行和列来填充它：
// loop through table rows
for i := 1; i <= numItems; i++ {
// loop through table columns
for w := 1; w <= capacity; w++ {
// do stuff in each element
}
}
然后，对于每个元素，我们将计算其对应的价值值。我们使用以下代码来实现这一点：
如果与当前行索引匹配的项的重量在当前列表示的重量范围内，则取以下两者中的最大值：
- 袋子里已有物品的总价值，或者，
- 袋子中除上一行索引处的物品外的所有物品的总价值，加上新物品的价值。
换句话说，当我们的算法考虑将某个物品放入购物袋时，我们要求它判断，在购物袋当前总重量下，将这个物品添加到购物袋中是否比之前添加的物品产生更高的总价值。如果这个物品是更好的选择，就把它放进去；否则，就把它取出来。
以下是实现此功能的代码：
// if weight of item matching this index can fit at the current capacity column...
if is[i-1].weight <= w {
// worth of this subset without this item
valueOne := float64(matrix[i-1][w])
// worth of this subset without the previous item, and this item instead
valueTwo := float64(is[i-1].worth + matrix[i-1][w-is[i-1].weight])
// take maximum of either valueOne or valueTwo
matrix[i][w] = int(math.Max(valueOne, valueTwo))
// if the new worth is not more, carry over the previous worth
} else {
matrix[i][w] = matrix[i-1][w]
}
比较物品组合的过程将持续进行，直到所有物品在背包总重量增加的每个可能阶段都被考虑在内。当以上所有情况都考虑完毕后，我们就枚举出了所有可能的总价值值，并将矩阵填充完毕。
我们将有一个很大的数字图表，最后一列最后一行将列出我们可能得到的最高值。
严格意义上对填充矩阵的表示。
这很棒，但是我们如何才能知道袋子里装的是哪些物品组合才能达到这个价值呢？
获取我们优化后的项目列表
为了确定哪些物品可以组合成最佳装箱单，我们需要反向检查矩阵，也就是从创建矩阵的相反方向开始。由于我们知道最大值位于最后一行最后一列，所以我们从那里开始。为了找到这些物品，我们：
- 获取当前单元格的值
- 将当前单元格的值与其正上方单元格的值进行比较。
- 如果数值不同，则说明袋子里的物品发生了变化；根据当前物品的重量，向后遍历各列，找到下一个要检查的单元格（找到添加当前物品之前袋子的重量）。
- 如果数值匹配，则背包物品没有变化；向上移动到上一行的单元格并重复上述步骤。
我们想要实现的操作的性质非常适合使用递归函数。如果你还记得我之前关于制作苹果派的文章，递归函数就是在特定条件下调用自身的函数。它的形式如下：
func checkItem(b *bag, i int, w int, is []item, matrix [][]int) {
if i <= 0 || w <= 0 {
return
}
pick := matrix[i][w]
if pick != matrix[i-1][w] {
b.addItem(is[i-1])
checkItem(b, i-1, w-is[i-1].weight, is, matrix)
} else {
checkItem(b, i-1, w, is, matrix)
}
}
checkItem()如果步骤 4 中描述的条件为真，我们的函数会调用自身。如果步骤 3 为真，它也会调用自身，但参数不同。
递归函数需要一个基本情况。在这个例子中，我们希望函数在遍历完所有值得比较的值后停止。因此，我们的基本情况是当i或w为真时0。
以下是动态规划方法整合后的样子：
func checkItem(b *bag, i int, w int, is []item, matrix [][]int) {
if i <= 0 || w <= 0 {
return
}
pick := matrix[i][w]
if pick != matrix[i-1][w] {
b.addItem(is[i-1])
checkItem(b, i-1, w-is[i-1].weight, is, matrix)
} else {
checkItem(b, i-1, w, is, matrix)
}
}
func dynamic(is []item, b *bag) *bag {
numItems := len(is) // number of items in knapsack
capacity := b.maxItemsWeight // capacity of knapsack
// create the empty matrix
matrix := make([][]int, numItems+1) // rows representing items
for i := range matrix {
matrix[i] = make([]int, capacity+1) // columns representing grams of weight
}
// loop through table rows
for i := 1; i <= numItems; i++ {
// loop through table columns
for w := 1; w <= capacity; w++ {
// if weight of item matching this index can fit at the current capacity column...
if is[i-1].weight <= w {
// worth of this subset without this item
valueOne := float64(matrix[i-1][w])
// worth of this subset without the previous item, and this item instead
valueTwo := float64(is[i-1].worth + matrix[i-1][w-is[i-1].weight])
// take maximum of either valueOne or valueTwo
matrix[i][w] = int(math.Max(valueOne, valueTwo))
// if the new worth is not more, carry over the previous worth
} else {
matrix[i][w] = matrix[i-1][w]
}
}
}
checkItem(b, numItems, capacity, is, matrix)
// add other statistics to the bag
b.totalWorth = matrix[numItems][capacity]
b.totalWeight = b.bagWeight + b.currItemsWeight
return b
}
动态规划结果
我们预期动态规划方法会比贪婪算法给出更优化的解决方案。结果如何呢？以下是结果：
背包及物品总重量： 6982克
包装物品总价值： 757
以下是我们的动态规划算法选择的物品，按价值排序：
| 物品 | 值得 | 重量 |
|---|---|---|
| 10条丁字裤 | 39 | 80 |
| 5 Under Armour 绑带 | 38 | 305 |
| 优衣库打底裤一条 | 37 | 185 |
| 2. Lululemon Cool Racerback | 36 | 174 |
| 迷你轰炸机旅行套装中的充电器和线缆 | 35 | 665 |
| 栖息处 | 34 | 170 |
| ThinkPad 紧凑型蓝牙键盘，带指点杆 | 33 | 460 |
| Seagate Backup Plus Slim | 32 | 159 |
| 1条黑色牛仔短裤 | 31 | 197 |
| 2条耐克专业短裤 | 30 | 112 |
| 2条 Lululemon 短裤 | 29 | 184 |
| 伊莎贝拉 T 字带鳄鱼凉鞋 | 28 | 200 |
| 2 件 Under Armour HeatGear CoolSwitch 背心 | 27 | 138 |
| 5双黑色袜子 | 26 | 95 |
| 2双 Injinji 女士跑步轻薄隐形五趾袜 | 25 | 54 |
| 1件漂亮的背心 | 24 | 71 |
| 1 件轻薄弹力长袖衬衫（Gap Fit 款） | 23 | 147 |
| 优衣库超轻羽绒服 | 22 | 235 |
| Patagonia Torrentshell | 21 | 301 |
| 轻便美利奴羊毛头巾 | 20 | 50 |
| 1 小黑裙（H&M） | 19 | 174 |
| Field Notes 纯黑色点阵备忘录 | 18 | 68 |
| Innergie PocketCell USB-C 6000mAh 移动电源 | 17 | 148 |
| 重要文件 | 16 | 228 |
| Deuter急救包（主动式） | 15 | 144 |
| 斯坦利经典真空保温露营杯 16 盎司 | 14 | 454 |
| JBL Reflect Mini 蓝牙运动耳机 | 13 | 14 |
| Anker SoundCore nano 蓝牙音箱 | 12 | 80 |
| Oakley Latch 太阳镜 | 11 | 30 |
| 雷朋 Wayfarer Classic | 10 | 45 |
| Petzl E+LITE 应急头灯 | 8 | 27 |
| Peak Design Cuff 相机腕带 | 6 | 26 |
| Travelon 微型秤 | 5 | 125 |
| 人形齿轮 GoBites Duo | 3 | 22 |
我们的动态规划解决方案明显优于贪婪算法的方案。我们的总价值为 757 分，比贪婪算法的 716 分高出 41 分，而且重量还轻了几克！
输入排序顺序
在测试我的动态规划解决方案时，我在将输入数据传递给函数之前，先对输入数据应用了Fisher-Yates 洗牌算法，以确保答案不会受到输入数据排序顺序的影响。以下是 Go 语言中洗牌算法的实现：
rand.Seed(time.Now().UnixNano())
for i := range itemList {
j := rand.Intn(i + 1)
itemList[i], itemList[j] = itemList[j], itemList[i]
}
当然，我后来意识到 Go 1.10 现在内置了 shuffle 功能……它的工作方式完全相同，看起来是这样的：
rand.Shuffle(len(itemList), func(i, j int) {
itemList[i], itemList[j] = itemList[j], itemList[i]
})
那么，物品的处理顺序是否影响了结果呢？嗯……
突然……出现了一个不速之客！
结果发现，答案在某种程度上确实取决于输入的顺序。当我多次运行动态规划算法时，有时会看到袋子的总重量不同，但总价值仍然是 757。起初我以为这是个 bug，但后来我仔细检查了与这两个不同总重量值对应的两组物品。除了几处细微的差别外，其他一切都相同，而这些差别加起来却导致了物品子集的不同，占总价值 757 分中的 14 分。
在这种情况下，仅基于最高总价值这一成功指标，存在两个同样最优的解。打乱输入似乎会影响矩阵中元素的排列位置，从而影响函数checkItem()遍历矩阵寻找目标元素的路径。由于两个元素集中最高总价值的成功指标相同，因此我们并非只有一个唯一的解——而是有两个！
作为一项学术练习，这两组物品都是正确答案。我们可以选择通过另一个指标进一步优化，例如所有物品的总重量。在重量尽可能轻的情况下获得最高价值，可以被视为理想解决方案。
以下是第二个更轻量级的动态规划结果：
包和物品总重量： 6955克
包装物品总价值： 757
| 物品 | 值得 | 重量 |
|---|---|---|
| 10条丁字裤 | 39 | 80 |
| 5 Under Armour 绑带 | 38 | 305 |
| 优衣库打底裤一条 | 37 | 185 |
| 2. Lululemon Cool Racerback | 36 | 174 |
| 迷你轰炸机旅行套装中的充电器和线缆 | 35 | 665 |
| 栖息处 | 34 | 170 |
| ThinkPad 紧凑型蓝牙键盘，带指点杆 | 33 | 460 |
| Seagate Backup Plus Slim | 32 | 159 |
| 1条黑色牛仔短裤 | 31 | 197 |
| 2条耐克专业短裤 | 30 | 112 |
| 2条 Lululemon 短裤 | 29 | 184 |
| 伊莎贝拉 T 字带鳄鱼凉鞋 | 28 | 200 |
| 2 件 Under Armour HeatGear CoolSwitch 背心 | 27 | 138 |
| 5双黑色袜子 | 26 | 95 |
| 2双 Injinji 女士跑步轻薄隐形五趾袜 | 25 | 54 |
| 1件漂亮的背心 | 24 | 71 |
| 1 件轻薄弹力长袖衬衫（Gap Fit 款） | 23 | 147 |
| 优衣库超轻羽绒服 | 22 | 235 |
| Patagonia Torrentshell | 21 | 301 |
| 轻便美利奴羊毛头巾 | 20 | 50 |
| 1 小黑裙（H&M） | 19 | 174 |
| Field Notes 纯黑色点阵备忘录 | 18 | 68 |
| Innergie PocketCell USB-C 6000mAh 移动电源 | 17 | 148 |
| 重要文件 | 16 | 228 |
| Deuter急救包（主动式） | 15 | 144 |
| JBL Reflect Mini 蓝牙运动耳机 | 13 | 14 |
| Anker SoundCore nano 蓝牙音箱 | 12 | 80 |
| Oakley Latch 太阳镜 | 11 | 30 |
| 雷朋 Wayfarer Classic | 10 | 45 |
| 洗漱用品拉链袋 | 9 | 236 |
| Petzl E+LITE 应急头灯 | 8 | 27 |
| Peak Design Cuff 相机腕带 | 6 | 26 |
| Travelon 微型秤 | 5 | 125 |
| BlitzWolf 蓝牙三脚架/独脚架 | 4 | 150 |
| 人形齿轮 GoBites Duo | 3 | 22 |
| Vapur 1升装水瓶 | 1 | 41 |
哪种方法更好？
进行基准测试
Go 标准库的testing包使得我们可以轻松地对这两种方法进行基准测试。我们可以了解每种算法的运行时间和内存使用量。以下是一个简单的示例main_test.go文件：
package main
import (
"testing"
)
func Benchmark_greedy(b *testing.B) {
itemList := readItems("objects.csv")
for i := 0; i < b.N; i++ {
minaal := bag{bagWeight: 1415, currItemsWeight: 0, maxItemsWeight: 5585}
greedy(itemList, minaal)
}
}
func Benchmark_dynamic(b *testing.B) {
itemList := readItems("objects.csv")
for i := 0; i < b.N; i++ {
minaal := bag{bagWeight: 1415, currItemsWeight: 0, maxItemsWeight: 5585}
dynamic(itemList, &minaal)
}
}
我们可以运行程序go test -bench=. -benchmem来查看这些结果：
Benchmark_greedy-4 1000000 1619 ns/op 2128 B/op 9 allocs/op
Benchmark_dynamic-4 1000 1545322 ns/op 2020332 B/op 49 allocs/op
贪婪算法性能
在运行贪婪算法 100 万次后，该算法的运行速度被可靠地测量为 0.001619 毫秒（换句话说：非常快）。它需要 2128 字节（约 2 千字节）的内存，并且每次迭代需要 9 次不同的内存分配。
动态规划性能
动态规划算法运行了 1000 次。测得其运行时间为 1.545322 毫秒或 0.001545322 秒（也就是说：仍然相当快）。每次迭代需要 2,020,332 字节或约 2 兆字节的内存，以及 49 次不同的内存分配。
判决
选择合适的编程问题解决方法，需要考虑输入数据集的大小。在本例中，数据集很小。在这种情况下，单遍贪心算法总是比动态规划算法更快、资源消耗更少，原因很简单，因为它步骤更少。我们的贪心算法比动态规划算法快了近两个数量级，内存占用也更低。
然而，如果没有这些额外的步骤，就意味着贪婪算法不太可能得到最佳解决方案。
很明显，动态规划算法给出了更好的结果：权重更低，总价值更高。
| 贪婪算法 | 动态规划 | |
|---|---|---|
| 总重量： | 6987克 | 6955克 |
| 总价值： | 716 | 757 |
动态规划在处理小数据集时虽然性能不足，但其优化能力却很强。问题在于，这种额外的优化是否值得以性能为代价。
当然，“更好”是一个主观判断。如果速度和低资源占用是我们衡量成功的标准，那么贪婪算法显然更胜一筹。如果背包里物品的总价值是我们衡量成功的标准，那么动态规划算法显然更胜一筹。然而，我们的场景更贴近实际，而这些算法设计中只有一种返回的结果是我会选择的。动态规划算法在优化背包里物品总价值最大化的过程中，漏掉了我价值最高但也最重的物品：我的笔记本电脑。没有它，附带的充电器、线缆、Roost支架和键盘都没什么用处。
更好的算法设计
有一种简单的方法可以修改动态规划方法，使笔记本电脑始终包含在内：我们可以修改数据，使笔记本电脑的价值大于所有其他物品价值的总和。（试试看！）
或许在重新设计动态规划算法使其更实用时，我们可以选择另一种更能反映物品重要性的成功指标，而不是主观的价值值。有很多指标可以用来表示物品的价值。以下是一些不错的替代指标示例：
- 使用该物品所花费的时间
- 购买该物品的初始成本
- 如果物品今天丢失，更换成本是多少？
- 使用该物品的产品的美元价值
同样地，使用这些替代指标之一，贪婪算法的结果可能会得到改善。
除了选择合适的方法来解决背包问题之外，将实际场景转化为代码来设计算法也很有帮助。
关于如何设计更优的算法，需要考虑的因素很多，超出了这篇入门文章的范围，我计划在后续文章中探讨（部分）相关内容。未来的算法或许能够决定我下次旅行的行李内容，但我们距离那一步还很遥远。敬请期待！
感谢阅读！希望这篇文章能让您更好地了解这两种常用方法的工作原理。我将在以后的文章中介绍分支定界法和时间复杂度。
如果你想了解更多关于我如何只用一个随身行李包生活的信息，请访问我的游牧博客herOneBag.com。
祝你今天过得非常愉快！:)
文章来源：https://dev.to/victoria/knapsack-problem-algorithms-for-my-real-life-carry-on-knapsack-33jj