中文
devexamples

Knapsack 01 Dynamic Programming (Go)

Solve the 0-1 knapsack problem in Go using dynamic programming with a rolling array for space optimization.

GoData Integrity

Code

snippet
package main

func knapsack01(weights, values []int, capacity int) int {
	n := len(weights)
	dp := make([]int, capacity+1)
	for i := 0; i < n; i++ {
		next := make([]int, capacity+1)
		for w := 0; w <= capacity; w++ {
			next[w] = dp[w]
			if w >= weights[i] && dp[w-weights[i]]+values[i] > next[w] {
				next[w] = dp[w-weights[i]] + values[i]
			}
		}
		dp = next
	}
	return dp[capacity]
}

Related Examples