编辑代码

package main

import (
	"fmt"
)

func optimizeKnapsack(capacity int, fruits []Fruit) {
	n := len(fruits)
	dp := make([][]int, n+1)

	for i := range dp {
		dp[i] = make([]int, capacity+1)
	}

	for i := 1; i <= n; i++ {
		for j := 0; j <= capacity; j++ {
			dp[i][j] = dp[i-1][j]
			if j >= fruits[i-1].Weight {
				dp[i][j] = max(dp[i][j], dp[i-1][j-fruits[i-1].Weight]+fruits[i-1].Value)
			}
		}
	}

	// 回溯获取最大价值对应的装水果策略
	selectedFruits := make([]Fruit, 0)
	i, j := n, capacity
	for i > 0 && j > 0 {
		if dp[i][j] != dp[i-1][j] {
			selectedFruits = append(selectedFruits, fruits[i-1])
			j -= fruits[i-1].Weight
		}
		i--
	}

	// 打印结果
	fmt.Println("装水果的策略：")
	for i := len(selectedFruits) - 1; i >= 0; i-- {
		fmt.Printf("%s\t重量：%dkg\t价值：%d元\n", selectedFruits[i].Name, selectedFruits[i].Weight, selectedFruits[i].Value)
	}
	fmt.Printf("总价值：%d元\n", dp[n][capacity])
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

type Fruit struct {
	Name   string
	Weight int
	Value  int
}

func main() {
	capacity := 20
	fruits := []Fruit{
		{"苹果", 15, 300},
		{"香蕉", 18, 180},
		{"橘子", 10, 150},
		{"猕猴桃", 9, 270},
	}

	optimizeKnapsack(capacity, fruits)
}