Golang 接受一组物品的重量和价值以及背包的最大容重

在这个Go语言文章中，我们将编写程序，接受一组物品的重量和价值以及背包的最大容重。背包问题是一个使用动态规划的优化问题。在这里，目的是找出可以放入背包的物品集合，同时不超过其容重或最大重量。

动态规划涉及将问题分解为较小的子问题并将它们组合以获得最佳解决方案。

语法

func make ([] type, size, capacity)

go语言中的make函数用于创建数组/映射，它接受要创建的变量的类型、大小和容量作为参数。

func len(v Type) int

len()函数用于获得任何参数的长度。它接受一个参数作为数据类型的变量，我们希望找到其长度，并返回整数值，该值是变量的长度。

步骤

此程序会在程序中导入必要的包fmt和main。
创建一个名为Item的结构类型，其中包含两个字段item和value，都是int类型。
创建一个名为knapsack的函数，该函数接受一个项目数组和容量作为输入参数。
此函数返回在给定容量内可以实现的最大值。
在此步骤中，使用make函数创建名为dp的二维切片来存储动态规划表。
该表具有len(items)+1行和capacity+1列。
在此步骤中，将表的第一行和第一列初始化为零，因为它们表示没有选择任何项目或容量为零的情况。
使用两个嵌套循环迭代项目和容量，检查当前项目的重量是否小于或等于当前容量，然后计算最大值：（items[i-1].value + dp[i-1][j-items[i-1].weight]，dp[i-1][j]）。
但是，如果当前项目的重量大于当前容量，则不能包含在内。在这种情况下，最大值保持与上一行相同。
循环结束后，最大值和容量将存储在dp[len(items)][capacity]中。
返回该值。
在此步骤中，实现一个名为max的函数，它接受两个整数并返回两者中的最大值。
创建一个名为main的函数。
在main函数中，初始化weights、values和items的容量。
在此步骤中，使用make函数创建一个与weights长度相等的item切片。
使用for循环根据提供的weights和values填充切片。
在此步骤中，使用items和capacity调用knapsack函数，并将输出赋值给名为maxValue的变量。
最后，使用来自fmt包的Println函数在控制台上打印最大值，其中ln表示换行。

示例

在此示例中，我们将编写一个Golang程序，该程序根据动态规划方法，接受一系列物品的重量和价值列表以及背包的最大重量容量。

package main

import (
    "fmt"
)

type Item struct {
    weight int
    value  int
}
func knapsack(items []Item, capacity int) int { 
    dp := make([][]int, len(items)+1)
    for i := 0; i <= len(items); i++ {
        dp[i] = make([]int, capacity+1)
    }
    for i := 1; i <= len(items); i++ {
        for j := 1; j <= capacity; j++ {            
            if items[i-1].weight <= j {     
                dp[i][j] = max(items[i-1].value+dp[i-1][j-items[i-1].weight], dp[i-1][j])
            } else {        
                dp[i][j] = dp[i-1][j]
            }
        }
    }
    return dp[len(items)][capacity]
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func main() {
    weights := []int{2, 3, 4, 5}
    values := []int{3, 4, 5, 6}
    capacity := 5
    items := make([]Item, len(weights))
    for i := 0; i < len(weights); i++ {
        items[i] = Item{weight: weights[i], value: values[i]}
    }
    maxValue := knapsack(items, capacity)
    fmt.Println("Maximum value:", maxValue)
}