package main

import (
	"fmt"
)

// Barang struct
type Barang struct {
	name   string
	value  int
	weight int
}

// Fungsi Knapsack Problem
func knapsack(items []Barang, maxCapacity int) (int, []string) {
	n := len(items)
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, maxCapacity+1)
	}

	// Mengisi tabel DP
	for i := 1; i <= n; i++ {
		for w := 0; w <= maxCapacity; w++ {
			if items[i-1].weight <= w {
				dp[i][w] = max(dp[i-1][w], dp[i-1][w-items[i-1].weight]+items[i-1].value)
			} else {
				dp[i][w] = dp[i-1][w]
			}
		}
	}

	// Nilai maksimum yang bisa dicapai
	maxValue := dp[n][maxCapacity]

	// Mencari barang-barang yang diambil untuk mencapai nilai maksimum
	selectedItems := []string{}
	w := maxCapacity
	for i := n; i > 0; i-- {
		if dp[i][w] != dp[i-1][w] {
			selectedItems = append(selectedItems, items[i-1].name)
			w -= items[i-1].weight
		}
	}

	return maxValue, selectedItems
}

// Fungsi untuk mencari nilai maksimum dari dua bilangan
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	// Data barang
	items := []Barang{
		{"A", 45, 7},
		{"B", 35, 5},
		{"C", 25, 2},
		{"D", 40, 5},
		{"E", 55, 10},
		{"F", 35, 3},
		{"G", 75, 6},
	}

	// Kapasitas maksimum tas
	maxCapacity := 29

	// Menyelesaikan masalah Knapsack
	maxValue, selectedItems := knapsack(items, maxCapacity)

	// Menampilkan hasil
	fmt.Printf("Nilai maksimum: %d juta rupiah\n", maxValue)
	fmt.Println("Barang-barang yang dipilih:")
	for _, item := range selectedItems {
		fmt.Println(item)
	}
}