knapsack.go

// Tabulation
func tabulation_knapsack(weight, value []int, capacity, n int) int {
	table := make([][]int, n+1)
	
	for i := 0; i <= n; i++ {
		table[i] = make([]int, capacity+1)
	}
	
	for i := 0; i <= n; i++ {
		for j := 0; j <= capacity; j++ {
			if i == 0 || j == 0 {
				table[i][j] = 0
			} else if weight[i-1] <= j {
				table[i][j] = int(math.Max(float64(value[i-1]+table[i-1][j-weight[i-1]]), float64(table[i-1][j]))) // Accept the value as weight is acceptable.
			} else {
				table[i][j] = table[i-1][j] // Ignore the value is exceeded.
			}
		}
	}
	return table[n][capacity]
}

// Recursion
func recursive_knapsack(weight, value []int, capacity, n int) int {

	if n == 0 || capacity == 0 {
		return 0
	}

	if weight[n-1] <= capacity {
		return int(math.Max(float64(value[n-1]+recursive_knapsack(weight, value, capacity-weight[n-1], n-1)), float64(recursive_knapsack(weight, value, capacity, n-1))))
	} else if weight[n-1] > capacity { 
		return recursive_knapsack(weight, value, capacity, n-1)
	}

	return 1
}

// Memoization
func memoization_knapsack(weight, value []int, capacity, n int, table [][]int) int {
	if capacity == 0 || n == 0 {
		return 0
	}
	if table[capacity][n] != -1 {
		return table[capacity][n]
	}
	if weight[n-1] <= capacity {
		table[capacity][n] = int(math.Max(float64(value[n-1]+memoization_knapsack(weight, value, capacity-weight[n-1], n-1, table)), float64(memoization_knapsack(weight, value, capacity, n-1, table))))
		return table[capacity][n]
	} else if weight[n-1] > capacity {
		table[capacity][n] = memoization_knapsack(weight, value, capacity, n-1, table)
		return table[capacity][n]
	}
	return 1
}