2023年7月29日发(作者：)

使⽤ga算法解决背包问题_我如何使⽤算法解决现实⽣活中的⼿提背包的背包问题使⽤ga算法解决背包问题I’m a nomad and live out of one carry-on bag. This means that the total weight of all my worldly possessions must fallunder airline cabin baggage weight limits — usually 10kg. On some smaller airlines, however, this weight limit drops to onally, I have to decide not to bring something with me to adjust to the smaller weight limit.我是⼀个Nomad民族，只能靠⼀个⼿提包⽣活。 这意味着我所有世俗财产的总重量必须在机舱⾏李重量限制之内(通常为10公⽄)。 但是，在⼀些较⼩的航空公司上，此重量限制降⾄7kg。 有时，我必须决定不带东西以适应较⼩的体重限制。As a practical exercise, deciding what to leave behind (or get rid of altogether) entails laying out all my things and choosingwhich ones to keep. That decision is based on the item’s usefulness to me (its worth) and its weight.作为⼀项实践练习，决定留下什么(或完全摆脱掉)需要布置我所有的东西并选择要保留的东西。 该决定基于该商品对我的有⽤性(价值)和重量。Being a programmer, I’m aware that decisions like this could be made more efficiently by a computer. It’s done sofrequently and so ubiquitously, in fact, that many will recognize this scenario as the classic

packing problem or

knapsackproblem. How do I go about telling a computer to put as many important items in my bag as possible while coming in at orunder a weight limit of 7kg? With algorithms! Yay!作为程序员，我知道可以通过计算机更有效地做出这样的决定。 实际上，这样做是如此频繁且⽆处不在，以⾄于许多⼈都将这种情况视为经典的打包问题或背包问题。 在告诉我7公⽄或以下的重量时，如何让计算机将尽可能多的重要物品放⼊包中？ 有了算法！ 好极了！I’ll discuss two common approaches to solving the knapsack problem: one called a greedy algorithm, and another calleddynamic programming (a little harder, but better, faster, stronger…).我将讨论两种解决背包问题的常⽤⽅法：⼀种称为贪婪算法

，另⼀种称为动态编程 (难度更⾼，但更好，更快，更强……)。Let’s get to it.让我们开始吧。设置 (The set up)I prepared my data in the form of a CSV file with three columns: the item’s name (a string), a representation of its worth(an integer), and its weight in grams (an integer). There are 40 items in total. I represented worth by ranking each item from40 to 1, with 40 being the most important and 1 equating with something like “why do I even have this again?” (If you’venever listed out all your possessions and ranked them by order of how useful they are to you, I highly recommend you try can be a very revealing exercise.)我以CSV⽂件的形式准备了数据，该⽂件包括三列：商品名称(字符串)，商品价值(整数)和重量(克)(整数)的表⽰形式。 总共有40个项⽬。我通过将每⼀项从40排名为1来表⽰价值，其中40是最重要的，⽽1则等同于“为什么我还要再次拥有它？” (如果您从未列出所有财产，并按对您有多有⽤的顺序对其进⾏了排名，我强烈建议您尝试⼀下。这可能是⼀个⾮常有意义的练习。)Total weight of all items and bag: 9003g所有物品和袋⼦的总重量： 9003gBag weight: 1415g包重： 1415gAirline limit: 7000g航空公司限制： 7000gMaximum weight of items I can pack: 5585g我可以包装的最⼤物品重量： 5585gTotal possible worth of items: 820项⽬的总可能价值： 820The challenge: Pack as many items as the limit allows while maximizing the total worth.挑战：在最⼤限度地增加总价值的同时，包装尽可能多的物品。数据结构 (Data structures)读取⽂件 (Reading in a file)Before we can begin thinking about how to solve the knapsack problem, we have to solve the problem of reading in andstoring our data. Thankfully, the Go standard library’s io/ioutil package makes the first part straightforward.在开始考虑如何解决背包问题之前，我们必须解决读取和存储数据的问题。 幸运的是，Go标准库的io/ioutil软件包使第⼀部分变得简单。package mainimport ( "fmt" "io/ioutil")func check(e error) { if e != nil { panic(e) }}func readItems(path string) { dat, err := le(path) check(err) (string(dat))}The ReadFile() function takes a file path and returns the file’s contents and an error (nil if the call is successful) so we’vealso created a check() function to handle any errors that might be returned. In a real-world application, we probably wouldwant to do something more sophisticated than panic, but that’s not important right le()函数采⽤⽂件路径并返回⽂件内容和错误(如果调⽤成功，则返回nil )，因此我们还创建了⼀个check()函数来处理可能返回的任何错误。 在现实世界中的应⽤程序中，我们可能想做⼀些⽐panic更复杂的事情，但是现在这并不重要。创建⼀个结构 (Creating a struct)Now that we’ve got our data, we should probably do something with it. Since we’re working with real-life items and a real-life bag, let’s create some types to represent them and make it easier to conceptualize our program. A struct in Go is atyped collection of fields. Here are our two types:现在我们已经有了数据，我们可能应该对它进⾏⼀些处理。 由于我们正在处理现实⽣活中的物品和⽣活中的包，因此让我们创建⼀些类型来表⽰它们，并使概念化我们的程序更加容易。 Go中的struct是字段的类型化集合。 这是我们的两种类型：type item struct { name string worth, weight int}type bag struct { bagWeight, currItemsWeight, maxItemsWeight, totalWeight int items []item}It is helpful to use field names that are very descriptive. You can see that the structs are set up just as we’ve described thethings they represent. An item has a name (string), and a worth and weight (integers). A bag has several fields of type intrepresenting its attributes, and also has the ability to hold items, represented in the struct as a slice of item typethingamabobbers.使⽤描述性很强的字段名称会有所帮助。 您可以看到这些结构已经建⽴，就像我们描述它们所代表的事物⼀样。 item具有name (字符串)，worth和weight (整数)。 bag具有表⽰其属性的int类型的⼏个字段，还具有容纳items的能⼒，该对象在struct中表⽰为item类型的东西thingamabobbers。解析和存储我们的数据 (Parsing and storing our data)Several comprehensive Go packages exist that we could use to parse our CSV data… but where’s the fun in that? Let’sgo basic with some string splitting and a for loop. Here’s our updated readItems() function:我们可以使⽤⼏个全⾯的Go包来解析CSV数据……但是，这样做的乐趣何在？ 让我们开始⼀些字符串拆分和for循环的基本操作。 这是我们更新的readItems()函数：func readItems(path string) []item {

dat, err := le(path) check(err) lines := (string(dat), "n") itemList := make([]item, 0) for i, v := range lines { if i == 0 { continue } s := (v, ",") newItemWorth, _ := (s[1]) newItemWeight, _ := (s[2]) newItem := item{name: s[0], worth: newItemWorth, weight: newItemWeight} itemList = append(itemList, newItem) } return itemList}Using , we split our dat on newlines. We then create an empty itemList to hold our items.使⽤ ，我们将dat换⾏。 然后，我们创建⼀个空的itemList来保存我们的项⽬。In our for loop, we skip the first line of our CSV file (the headers) then iterate over each line. We use (read “A toi”) to convert the values for each item’s worth and weight into integers. We then create a newItem with these field valuesand append it to the itemList. Finally, we return itemList.在for循环中，我们跳过CSV⽂件的第⼀⾏(标头)，然后遍历每⾏。 我们使⽤ (读为“ A to i”)将每个物品的价值和重量的值转换为整数。 然后，我们使⽤这些字段值创建⼀个newItem ，并将其附加到itemList 。 最后，我们返回itemList 。Here’s what our set up looks like so far:到⽬前为⽌，这是我们的设置：package mainimport ( "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 := le(path) check(err) lines := (string(dat), "n") itemList := make([]item, 0) for i, v := range lines { if i == 0 { continue // skip the headers on the first line } s := (v, ",") newItemWorth, _ := (s[1]) newItemWeight, _ := (s[2]) newItem := item{name: s[0], worth: newItemWorth, weight: newItemWeight} itemList = append(itemList, newItem) } return itemList}Now that we’ve got our data structures set up, let’s get packing (?) on the first approach.现在我们已经建⽴了数据结构，让我们在第⼀种⽅法上打包(？)。贪⼼算法 (Greedy algorithm)A greedy algorithm is the most straightforward approach to solving the knapsack problem, in that it is a one-pass algorithmthat constructs a single final solution. At each stage of the problem, the greedy algorithm picks the option that is locallyoptimal, meaning it looks like the most suitable option right now. It does not revise its previous choices as it progressesthrough our data set.贪⼼算法是解决背包问题的最直接⽅法，因为它是构造单个最终解决⽅案的单次通过算法。 在问题的每个阶段，贪婪算法都会选择局部最优的选项，这意味着它看起来像是⽬前最合适的选项。 它在处理数据集时不会修改其先前的选择。建⽴我们的贪婪算法 (Building our greedy algorithm)The steps of the algorithm we’ll use to solve our knapsack problem are:⽤于解决背包问题的算法步骤如下：1. Sort items by worth, in descending order.按价值按降序对项⽬进⾏排序。2. Start with the highest worth item. Put items into the bag until the next item on the list cannot fit.从价值最⾼的物品开始。 将物品放⼊包中，直到列表中的下⼀个物品⽆法容纳为⽌。3. Try to fill any remaining capacity with the next item on the list that can fit.尝试⽤列表中适合的下⼀项来填充所有剩余容量。If you read my , you’ll know that I always start by figuring out what the next most important question is. In this case, thereare three main operations we need to figure out how to do:如果您阅读了 ，您就会知道，我总是从弄清楚下⼀个最重要的问题开始。 在这种情况下，我们需要确定三个主要操作：Sort items by worth.按价值对项⽬进⾏排序。Put an item in the bag.在袋⼦⾥放⼀个东西。Check to see if the bag is full.检查袋⼦是否装满。The first one is just a docs lookup away. Here’s how we sort a slice in Go:第⼀个只是⽂档查找。 这是我们在Go中对切⽚进⾏排序的⽅式：(is, func(i, j int) bool { return is[i].worth > is[j].worth})The () function orders our items according to the less function we provide. In this case, it will order the highestworth items before the lowest worth ()函数根据我们提供的less函数对项⽬进⾏排序。 在这种情况下，它将在价值最低的商品之前订购价值最⾼的商品。Given that we don’t want to put an item in the bag if it doesn’t fit, we’ll complete the last two tasks in reverse. First,we’ll check to see if the item fits. If so, it goes in the bag.鉴于我们不想在不适合的情况下将其放⼊袋中，我们将反向完成最后两个任务。 ⾸先，我们将检查项⽬是否适合。 如果是这样，它放在袋⼦⾥。func (b *bag) addItem(i item) error { if emsWeight+ <= msWeight { emsWeight += = append(, i) return nil } return ("could not fit item")}Notice the * in our first line there. That indicates that bag is a pointer receiver (as opposed to a value receiver). It’s aconcept that can be slightly confusing if you’re new to Go. Here are that might help you decide when to use a valuereceiver and when to use a pointer receiver. For the purposes of our addItem() function, this case applies:请注意我们第⼀⾏中的* 。 这表明bag是指针接收器(与值接收器相对)。 如果您不熟悉Go，那么这个概念可能会使您感到困惑。 这⾥有可能会帮助您决定何时使⽤值接收器以及何时使⽤指针接收器。 就我们的addItem()函数⽽⾔，这种情况适⽤：If the method needs to mutate the receiver, the receiver must be a pointer.如果该⽅法需要更改接收⽅，则接收⽅必须是指针。Our use of a pointer receiver tells our function we want to operate on

this specific bag in particular, not a new bag. It’simportant because without it, every item would always fit in a newly created bag! A little detail like this can make thedifference between code that works and code that keeps you up until 4am chugging Red Bull and muttering to yourself. (Goto bed on time even if your code doesn’t work — you’ll thank me later.)我们使⽤指针接收器告诉我们的功能是我们要在特定的袋⼦上操作，⽽不是在新袋⼦上操作。 这很重要，因为没有它，所有物品都将始终装在新创建的包中！ 像这样的⼀些细节可以使有效的代码与使您⼀直⼯作到凌晨4点选择Red Bull并喃喃⾃语的代码有所不同。 (即使您的代码⽆效，也要准时上床睡觉-稍后您会感谢我的。)Now that we’ve got our components, let’s put together our greedy algorithm:现在我们有了组件，下⾯将我们的贪婪算法放在⼀起：func greedy(is []item, b bag) { (is, func(i, j int) bool { return is[i].worth > is[j].worth }) for i := range is { m(is[i]) } eight = ght + emsWeight for _, v := range { orth += }}Then in our main() function, we’ll create our bag, read in our data, and call our greedy algorithm. Here’s what it looks like,all set up and ready to go:然后，在main()函数中，我们将创建包，读取数据，然后调⽤贪婪算法。 如下所⽰，所有设置都已准备就绪，可以开始使⽤：func main() { minaal := bag{bagWeight: 1415, currItemsWeight: 0, maxItemsWeight: 5585} itemList := readItems("") greedy(itemList, minaal)}贪婪算法结果 (Greedy algorithm results)So how does this algorithm do when it comes to efficiently packing our bag to maximize its total worth? Here’s the result:那么，在有效包装⾏李以最⼤化其总价值时，该算法⼜如何呢？ 结果如下：Total weight of bag and items: 6987g包袋总重量： 6987gTotal worth of packed items: 716包装物品总价值： 716Here are the items our greedy algorithm chose, sorted by worth:这是我们的贪婪算法选择的项⽬，按价值排序：It’s clear that the greedy algorithm is a straightforward way to quickly find a feasible solution. For small data sets, it willprobably be close to the optimal solution. The algorithm packed a total item worth of 716 (104 points less than themaximum possible value), while filling the bag with just 13g left over.显然，贪婪算法是快速找到可⾏解决⽅案的直接⽅法。 对于⼩型数据集，它可能接近最佳解决⽅案。 该算法包装了总价值为716(⽐最⼤可能值低104点)的物品，同时仅剩13克装满了袋⼦。As we learned earlier, the greedy algorithm doesn’t improve upon the solution it returns. It simply adds the next highestworth item it can to the bag.如我们先前所知，贪婪算法在返回的解决⽅案上并没有改善。 它只是将可能的下⼀个最⾼价值的物品添加到包中。Let’s look at another method for solving the knapsack problem that will give us the optimal solution — the highest possibletotal worth under the weight limit.让我们看⼀下解决背包问题的另⼀种⽅法，该⽅法将为我们提供最佳解决⽅案-在重量限制范围内尽可能多的总价值。动态编程 (Dynamic programming)The name “dynamic programming” can be a bit misleading. It’s not a style of programming, as the name might causeyou to infer, but simply another approach.“动态编程”这个名称可能会引起误解。 这不是⼀种编程风格，因为名称可能会导致您进⾏推断，⽽只是另⼀种⽅法。Dynamic programming differs from the straightforward greedy algorithm in a few key ways. Firstly, a dynamic programmingbag packing solution enumerates the entire solution space with all possibilities of item combinations that could be used topack our bag. Where a greedy algorithm chooses the most optimal local solution, dynamic programming algorithms are ableto find the most optimal global solution.动态编程在⼀些关键⽅⾯与直接贪婪算法不同。 ⾸先，动态编程袋包装解决⽅案列举了整个解决⽅案空间，其中包括所有可能⽤于包装我们的袋的项⽬组合。 当贪婪算法选择最优的本地解决⽅案，动态编程算法都能够找到最优化的全球性解决⽅案。Secondly, dynamic programming uses memoization to store the results of previously computed operations and returns thecached result when the operation occurs again. This allows it to “remember” previous combinations. This takes less timethan it would to re-compute the answer again.其次，动态编程使⽤记忆存储先前计算的操作的结果，并在操作再次发⽣时返回缓存的结果。 这使它可以“记住”以前的组合。 与重新计算答案相⽐，此⽅法花费的时间更少。建⽴我们的动态编程算法 (Building our dynamic programming algorithm)To use dynamic programming to find the optimal recipe for packing our bag, we’ll need to:要使⽤动态编程来找到⽤于包装袋的最佳配⽅，我们需要：1. Create a matrix representing all subsets of the items (the solution space) with rows representing items and columnsrepresenting the bag’s remaining weight capacity创建⼀个矩阵，该矩阵表⽰项⽬的所有⼦集(解决⽅案空间)，其中⾏表⽰项⽬，⽽列表⽰袋的剩余重量2. Loop through the matrix and calculate the worth that can be obtained by each combination of items at each stage ofthe bag’s capacity遍历矩阵，并计算出在包容量的每个阶段中每种物品组合所能获得的价值3. Examine the completed matrix to determine which items to add to the bag in order to produce the maximum possibleworth for the bag in total检查完成的矩阵，确定要添加到袋⼦中的项⽬，以使袋⼦总价值最⼤化It will be most helpful to visualize our solution space. Here’s a representation of what we’re building with our code:可视化我们的解决⽅案空间将⾮常有帮助。 这是我们使⽤代码构建的表⽰：In Go, we can create this matrix as a slice of slices.在Go中，我们可以将此矩阵创建为切⽚的⼀部分。matrix := make([][]int, numItems+1) // rows representing itemsfor i := range matrix { matrix[i] = make([]int, capacity+1) // columns representing grams of weight}We’ve padded the rows and columns by 1 so that the indicies match the item and weight numbers.我们⽤1填充了⾏和列，以便索引与项⽬和重量数字匹配。Now that we’ve created our matrix, we’ll fill it by looping over the rows and the columns:现在我们已经创建了矩阵，我们将通过遍历⾏和列来填充它：// loop through table rowsfor i := 1; i <= numItems; i++ { // loop through table columns for w := 1; w <= capacity; w++ { // do stuff in each element }}Then for each element, we’ll calculate the worth value to ascribe to it. We do this with code that represents the followingprocess:然后，对于每个元素，我们将计算值得的价值。 我们使⽤代表以下过程的代码来做到这⼀点：If the item at the index matching the current row fits within the weight capacity represented by the current column, take themaximum of either:如果索引处与当前⾏匹配的项⽬符合当前列所表⽰的重量范围，则取最⼤值之⼀：The total worth of the items already in the bag or,⼿提袋中已有物品的总价值，或The total worth of all the items in the bag except the item at the previous row index, plus the new item’s worth.包中所有项⽬的总价值(上⼀⾏索引中的项⽬除外)加上新项⽬的价值。In other words, as our algorithm considers one of the items, we’re asking it to decide whether this item added to the bagwould produce a higher total worth than the last item it added to the bag, at the bag’s current total weight. If this currentitem is a better choice, put it in — if not, leave it out.换句话说，当我们的算法考虑其中⼀个项⽬时，我们要求它决定以当前袋⼦的总重量，添加到袋⼦中的这个项⽬是否会⽐添加到袋⼦中的最后⼀个项⽬产⽣更⾼的总价值。 如果当前的项⽬是更好的选择，则将其放⼊-否则，将其保留。Here’s the code that accomplishes this:这是完成此操作的代码：// if weight of item matching this index can fit at the current 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((valueOne, valueTwo))// if the new worth is not more, carry over the previous worth} else { matrix[i][w] = matrix[i-1][w]}This process of comparing item combinations will continue until every item has been considered at every possible stage ofthe bag’s increasing total weight. When all the above have been considered, we’ll have enumerated the solution space —filled the matrix — with all possible total worth values.⽐较项⽬组合的过程将继续进⾏，直到在袋⼦总重量增加的每个可能阶段都考虑了每个项⽬为⽌。 考虑以上所有因素后，我们将枚举所有可能的总价值值(⽤矩阵填充)的解决⽅案空间。We’ll have a big chart of numbers, and in the last column at the last row we’ll have our highest possible value.我们将有⼀个很⼤的数字图表，并且在最后⼀⾏的最后⼀列中，我们将获得可能的最⾼价值。That’s great, but how do we find out which combination of items were put in the bag to achieve that worth?太好了，但是我们如何找出包装中的哪些物品组合才能实现这⼀⽬标呢？获取我们的优化物品清单 (Getting our optimized item list)To see which items combine to create our optimal packing list, we’ll need to examine our matrix in reverse to the way wecreated it. Since we know the highest possible value is in the last row in the last column, we’ll start there. To find the items,we:要查看可以组合哪些物料以创建最佳装箱单，我们需要以与创建矩阵相反的⽅式检查矩阵。 由于我们知道最⾼的可能值位于最后⼀列的最后⼀⾏，因此我们将从此处开始。 为了找到物品，我们：1. Get the value of the current cell获取当前单元格的值2. Compare the value of the current cell to the value in the cell directly above it将当前单元格的值与其正上⽅的单元格中的值进⾏⽐较3. If the values differ, there was a change to the bag items. Find the next cell to examine by moving backwards throughthe columns according to the current item’s weight (find the value of the bag before this current item was added)如果值不同，则说明⾏李袋有所更改。 根据当前物品的重量，通过在列中向后移动来找到要检查的下⼀个单元格(在添加当前物品之前，找到袋⼦的值)4. If the values match, there was no change to the bag items. Move up to the cell in the row above and repeat如果值匹配，则袋项⽬没有变化。 向上移动到上⼀⾏的单元格，然后重复The nature of the action we’re trying to achieve lends itself well to a recursive function. If you recall from , recursivefunctions are simply functions that call themselves under certain conditions. Here’s what it looks like:我们尝试实现的操作的性质⾮常适合于递归函数。 如果您回想起 ，那么递归函数就是在某些条件下会⾃⾏调⽤的函数。 看起来是这样的：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] { m(is[i-1]) checkItem(b, i-1, w-is[i-1].weight, is, matrix) } else { checkItem(b, i-1, w, is, matrix) }}Our checkItem() function calls itself if the condition we described in step 4 is true. If step 3 is true, it also calls itself, but withdifferent arguments.如果我们在步骤4中描述的条件为true，则我们的checkItem()函数将⾃⾏调⽤。 如果第3步是正确的，则它也会调⽤⾃⼰，但带有不同的参数。Recursive functions require a base case. In this example, we want the function to stop once we run out of values of worth tocompare. Thus our base case is when either i or w are 0.递归函数需要⼀个基本情况。 在此⽰例中，我们希望函数在值得⽐较的值⽤完后停⽌运⾏。 因此，我们的基本情况是当i或w为0 。Here’s how the dynamic programming approach looks when it’s all put together:将所有这些放在⼀起时，动态编程⽅法的外观如下：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] { m(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 := msWeight // 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 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((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 orth = matrix[numItems][capacity] eight = ght + emsWeight return b}动态编程结果 (Dynamic programming results)We expect that the dynamic programming approach will give us a more optimized solution than the greedy algorithm. So didit? Here are the results:我们期望动态编程⽅法将⽐贪婪算法为我们提供更优化的解决⽅案。 是吗 结果如下：Total weight of bag and items: 6982g包袋总重量： 6982gTotal worth of packed items: 757包装物品总价值： 757Here are the items our dynamic programming algorithm chose, sorted by worth:这是我们的动态编程算法选择的项⽬，按价值排序：There’s an obvious improvement to our dynamic programming solution over what the greedy algorithm gave us. Our totalworth of 757 is 41 points greater than the greedy algorithm’s solution of 716, and for a few grams less weight too!与贪婪算法给我们的东西相⽐，我们的动态编程解决⽅案有了明显的改进。 我们的总价值757⽐贪婪算法的解决⽅案716⾼41点，⽽且重量也减少了⼏克！输⼊排序顺序 (Input sort order)While testing my dynamic programming solution, I implemented the on the input before passing it into my function, just toensure that the answer wasn’t somehow dependent on the sort order of the input. Here’s what the shuffle looks like inGo:在测试我的动态编程解决⽅案时，我在将输⼊传递给我的函数之前对输⼊执⾏了 ，只是为了确保答案不以某种⽅式取决于输⼊的排序顺序。 这是Go中洗牌的样⼦：(().UnixNano())for i := range itemList { j := (i + 1) itemList[i], itemList[j] = itemList[j], itemList[i]}Of course I then realized that Go 1.10 now has a built-in shuffle. It works precisely the same way and looks like this:当然，然后我意识到Go 1.10现在具有内置的随机播放功能。 它的⼯作⽅式完全相同，如下所⽰：e(len(itemList), func(i, j int) { itemList[i], itemList[j] = itemList[j], itemList[i]})So did the order in which the items were processed affect the outcome? Well…那么处理项⽬的顺序会影响结果吗？ 好…突然……流氓重物出现了！ (Suddenly… a rogue weight appears!)As it turns out, in a way, the answer did depend on the order of the input. When I ran my dynamic programming algorithmseveral times, I sometimes saw a different total weight for the bag, though the total worth remained at 757. I initially thoughtthis was a bug before examining the two sets of items that accompanied the two different total weight values. Everythingwas the same except for a few changes that collectively added up to a different item subset accounting for 14 of the 757worth points.事实证明，答案确实取决于输⼊的顺序。 当我多次运⾏动态编程算法时，有时我看到的袋⼦总重量有所不同，尽管总价值仍然为757。在检查两组带有两种不同总重量的物品之前，我最初认为这是⼀个错误。价值观。 除少数更改外，其他所有内容都相同，这些更改合计起来构成了757个价值点中的14个不同⼦集。In this case, there were two equally optimal solutions based only on the success metric of the highest total possible ing the input seemed to affect the placement of the items in the matrix and thus, the path that the checkItem() functiontook as it went through the matrix to find the chosen items. Since the success metric of having the highest possible worthwas the same in both item sets, we don’t have a single unique solution - there’s two!在这种情况下，仅基于最⼤可能总价值的成功指标，就有两个同等最佳的解决⽅案。 改组输⼊似乎会影响项⽬在矩阵中的位置，并因此影响checkItem()函数经过矩阵以查找所选项⽬时所采⽤的路径。 由于在两个项⽬集中具有最⾼价值的成功指标是相同的，所以我们没有⼀个唯⼀的解决⽅案-有两个！As an academic exercise, both these sets of items are correct answers. We may choose to optimize further by anothermetric, say, the total weight of all the items. The highest possible worth at the least possible weight could be seen as an idealsolution.作为⼀项学术练习，这两组项⽬都是正确的答案。 我们可能会选择通过另⼀个指标(即所有商品的总重量)进⼀步优化。 以最⼩的重量获得尽可能⾼的价值被视为理想的解决⽅案。Here’s the second, lighter, dynamic programming result:这是第⼆个更轻松的动态编程结果：Total weight of bag and items: 6955g包袋总重量： 6955gTotal worth of packed items: 757包装物品总价值： 757哪种⽅法更好？ (Which approach is better?)进⾏基准测试 (Go benchmarking)The Go standard library’s testing package makes it straightforward for us to these two approaches. We can find out howlong it takes each algorithm to run, and how much memory each uses. Here’s a simple main_ file:Go标准库的testing包使我们可以轻松地对这两种⽅法进⾏ 。 我们可以找出每种算法运⾏需要多长时间，以及每种使⽤多少内存。 这是⼀个简单的main_⽂件：package mainimport ( "testing")func Benchmark_greedy(b *testing.B) { itemList := readItems("") 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("") for i := 0; i < b.N; i++ { minaal := bag{bagWeight: 1415, currItemsWeight: 0, maxItemsWeight: 5585} dynamic(itemList, &minaal) }}We can run go test -bench=. -benchmem to see these results:我们可以运⾏go test -bench=. -benchmem go test -bench=. -benchmem查看以下结果：Benchmark_greedy-4 1000000 1619 ns/op 2128 B/op 9 allocs/opBenchmark_dynamic-4 1000 1545322 ns/op 2020332 B/op 49 allocs/op贪婪算法性能 (Greedy algorithm performance)After running the greedy algorithm 1,000,000 times, the speed of the algorithm was reliably measured to be 0.001619milliseconds (translation: very fast). It required 2128 Bytes or 2-ish kilobytes of memory and 9 distinct memory allocationsper iteration.在运⾏贪婪算法1,000,000次之后，该算法的速度被可靠地测量为0.001619毫秒(转换：⾮常快)。 每次迭代需要2128字节或2千KB的内存，并且需要9种不同的内存分配。动态编程性能 (Dynamic programming performance)The dynamic programming algorithm was run 1,000 times. Its speed was measured to be 1.545322 milliseconds or0.001545322 seconds (translation: still pretty fast). It required 2,020,332 Bytes or 2-ish Megabytes, and 49 distinctmemory allocations per iteration.动态编程算法运⾏了1000次。 测得其速度为1.545322毫秒或0.001545322秒(转换：仍相当快)。 它需要2,020,332字节或2兆字节，并且每次迭代需要49个不同的内存分配。判决 (The verdict)Part of choosing the right approach to solving any programming problem is taking into account the size of the input dataset. In this case, it’s a small one. In this scenario, a one-pass greedy algorithm will always be faster and less resource-needy than dynamic programming, simply because it has fewer steps. Our greedy algorithm was almost two orders ofmagnitude faster and less memory-hungry than our dynamic programming algorithm.选择正确的⽅法来解决任何编程问题的⼀部分，就是要考虑输⼊数据集的⼤⼩。 在这种情况下，它很⼩。 在这种情况下，单遍贪婪算法总是⽐动态编程更快，资源占⽤更少，这仅仅是因为它的步骤更少。 我们的贪婪算法⽐我们的动态编程算法快了近两个数量级，并且减少了内存消耗。Not having those extra steps, however, means that getting the best possible solution from the greedy algorithm is unlikely.但是，没有这些额外的步骤意味着从贪婪算法中获得最佳解决⽅案的可能性很⼩。It’s clear that the dynamic programming algorithm gave us better numbers: a lower weight, and higher overall worth.显然，动态编程算法为我们提供了更好的数字：更轻的重量和更⾼的整体价值。贪⼼算法 (Greedy algorithm)Total weight: 6987g总重量：6987gTotal worth: 716总价值：716动态编程 (Dynamic programming)Total weight: 6955g总重量：6955gTotal worth: 757总价值：757Where dynamic programming on small data sets lacks in performance, it makes up in optimization. The question thenbecomes whether that additional optimization is worth the performance cost.⼩数据集上的动态编程缺乏性能，⽽优化则由其弥补。 然后，问题就在于，是否进⾏额外的优化是否值得付出性能成本。“Better,” of course, is a subjective judgement. If speed and low resource usage is our success metric, then the greedyalgorithm is clearly better. If the total worth of items in the bag is our success metric, then dynamic programming is clearlybetter.当然，“更好”是⼀种主观判断。 如果速度和低资源使⽤率是我们的成功指标，那么贪婪算法显然更好。 如果袋中物品的总价值是我们的成功指标，那么动态编程显然会更好。However, our scenario is a practical one, and only one of these algorithm designs returned an answer I’d choose. Inoptimizing for the overall greatest possible total worth of the items in the bag, the dynamic programming algorithm left outmy highest-worth, but also heaviest, item: my laptop. The chargers and cables, Roost stand, and keyboard that wereincluded aren’t much use without it.但是，我们的场景是⼀个实际的场景，这些算法设计中只有⼀个返回了我选择的答案。 在优化袋⼦中所有物品的最⼤总价值时，动态编程算法忽略了我最有价值但也最重的物品：我的笔记本电脑。 没有它，充电器和电缆，Roost⽀架和键盘就没什么⽤了。更好的算法设计 (Better algorithm design)There’s a simple way to alter the dynamic programming approach so that the laptop is always included: we can modify thedata so that the worth of the laptop is greater than the sum of the worth of all the other items. (Try it out!)有⼀种简单的⽅法可以更改动态编程⽅法，以便始终包含便携式计算机：我们可以修改数据，以使便携式计算机的价值⼤于所有其他项⽬的价值之和。 (试试看！)Perhaps in re-designing the dynamic programming algorithm to be more practical, we might choose another success metricthat better reflects an item’s importance, instead of a subjective worth value. There are many possible metrics we can useto represent the value of an item. Here are a few examples of a good proxy:也许在重新设计动态编程算法以使其更实⽤时，我们可能会选择另⼀个更好地反映项⽬重要性的成功指标，⽽不是主观的价值。 我们可以使⽤许多可能的指标来表⽰项⽬的价值。 以下是⼀些良好代理的⽰例：Amount of time spent using the item使⽤该物品花费的时间Initial cost of purchasing the item购买物品的初始费⽤Cost of replacement if the item were lost today今天丢失的物品的更换费⽤Dollar value of the product of using the item使⽤该物品的产品的美元价值By the same token, the greedy algorithm’s results might be improved with the use of one of these alternate metrics.同样，贪婪算法的结果可能会通过使⽤这些替代指标之⼀⽽得到改善。On top of choosing an appropriate approach to solving the knapsack problem in general, it is helpful to design ouralgorithm in a way that translates the practicalities of a scenario into code.除了选择合适的⽅法来解决背包问题外，以⼀种将⽅案的实际性转化为代码的⽅式设计我们的算法是有帮助的。There are many considerations for better algorithm design beyond the scope of this introductory post that I plan to cover(some of) in later articles. A future algorithm may very well decide my bag’s contents on the next trip, but we’re not quitethere yet. Stay tuned!我打算在以后的⽂章中(其中的⼀些)介绍这篇介绍性⽂章之外的内容，因此有很多考虑因素需要更好的算法设计。 未来的算法很可能会在下次旅⾏中决定我的⾏李的内容，但我们还没有完全确定。 敬请关注！Thanks for reading! I hope this article has given you a better idea of how these two common approaches work. If you’d liketo learn more about how I live out of one carry-on bag, check out my nomad blog at .谢谢阅读！

我希望本⽂能使您更好地了解这两种常见⽅法的⼯作⽅式。

如果您想了解更多关于我如何⽤⼀个⼿提袋⽣活的信息，请在上查看我的Nomad博客。Have a really great day. :)祝您有美好的⼀天。

:)使⽤ga算法解决背包问题