You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
74 lines
1.1 KiB
74 lines
1.1 KiB
package main
|
|
|
|
import (
|
|
"golang.org/x/exp/constraints"
|
|
)
|
|
|
|
type Book struct {
|
|
Weight int
|
|
Value int
|
|
}
|
|
|
|
func MaxValue(capacity int, books []Book) int {
|
|
if capacity == 0 {
|
|
return 0
|
|
}
|
|
if len(books) == 0 {
|
|
return 0
|
|
}
|
|
|
|
book, rest := books[0], books[1:]
|
|
withBook := book.Value + MaxValue(capacity-book.Weight, rest)
|
|
withoutBook := MaxValue(capacity, rest)
|
|
if book.Weight > capacity {
|
|
return withoutBook
|
|
}
|
|
|
|
return Max(withBook, withoutBook)
|
|
}
|
|
|
|
func DynamicMaxValue(capacity int, books []Book) int {
|
|
memo := make([]int, capacity+1)
|
|
|
|
for _, book := range books {
|
|
for c := capacity; c >= 0; c-- {
|
|
if book.Weight <= c {
|
|
memo[c] = Max(memo[c], memo[c-book.Weight]+book.Value)
|
|
}
|
|
}
|
|
}
|
|
|
|
return memo[capacity]
|
|
|
|
}
|
|
|
|
func main() {
|
|
println("Did it")
|
|
}
|
|
func Max[T constraints.Ordered](args ...T) T {
|
|
if len(args) == 0 {
|
|
return *new(T) // zero value of T
|
|
}
|
|
|
|
if isNan(args[0]) {
|
|
return args[0]
|
|
}
|
|
|
|
max := args[0]
|
|
for _, arg := range args[1:] {
|
|
|
|
if isNan(arg) {
|
|
return arg
|
|
}
|
|
|
|
if arg > max {
|
|
max = arg
|
|
}
|
|
}
|
|
return max
|
|
}
|
|
|
|
func isNan[T constraints.Ordered](arg T) bool {
|
|
return arg != arg
|
|
}
|