資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究一個使用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 表示換行符。
示例
在此示例中，我們將編寫一個 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)
}
輸出
Maximum value : 7
結論
我們編譯並執行了使用動態規劃方法接收物品的重量和價值列表以及揹包的最大重量容量的 Golang 程式。
193 次瀏覽
