一个使用Golang编写的程序，接收物品的重量和价值列表以及背包的最大重量容量

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

动态规划涉及通过将问题分解成更小的子问题，然后将它们组合起来以获得最优解来解决问题。

语法

func make ([] type, size, capacity)

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

func len(v Type) int

len() 函数用于获取任何参数的长度。它将要查找长度的数据类型变量作为参数，并返回一个整数，该整数是变量的长度。

算法

  • 此程序在程序中导入了必要的包 fmt 和 main。

  • 创建一个名为 Item 的结构体类型，其中包含两个字段：item 的重量和价值，它们都是 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 中，初始化物品的重量、价值和容量。

  • 在此步骤中，使用 make 函数创建一个与重量长度相等的物品切片。

  • 使用 for 循环根据提供的重量和价值填充切片。

  • 在此步骤中，使用物品和容量调用 knapsack 函数，并将输出分配给名为 maxValue 的变量。

  • 最后，使用 fmt 包中的 Println 函数在控制台上打印最大值，其中 ln 表示换行符。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

示例

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

Open Compiler
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)
}

输出

Maximum value : 7

结论

我们编译并执行了使用动态规划方法接收物品的重量和价值列表以及背包的最大重量容量的 Golang 程序。

更新于: 2023年8月4日

193 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告