Golang实现0-1背包问题方案(动态规划-贪心算法-回溯-分支定界)

算法实现说明

• 动态规划算法时间复杂度较低，能够求解较大规模的问题，但空间复杂度较高，不适用于数据量较大的问题。
• 贪心算法时间复杂度较低，能够求解较大规模的问题，但不能保证求得的解是最优解。
• 回溯算法能够求解较小规模的问题，但时间复杂度较高，不适用于数据量较大的问题。
• 分支定界算法能够求解较小规模的问题，但时间复杂度较高，不适用于数据量较大的问题。

0-1背包问题说明

0-1背包问题是一个经典的组合优化问题，其问题描述如下：

有一个容量为 $C$ 的背包，和 $n$ 个物品，每个物品有重量 $w_i$ 和价值 $v_i$，现在需要从这 $n$ 个物品中选择一些物品放入背包中，使得这些物品的总重量不超过 $C$，且这些物品的总价值最大。

0-1背包问题是一个 NP 完全问题，因此不存在多项式时间复杂度的算法能够求解该问题。但是，我们可以使用多种算法来求解该问题，包括动态规划、贪心、回溯、分支定界算法等。

动态规划算法

动态规划算法是求解0-1背包问题的一种常用算法，其时间复杂度较低，能够求解较大规模的问题。动态规划算法的基本思想是将原问题分解为若干个子问题，先求解子问题，再由子问题的解得到原问题的解。

动态规划算法求解0-1背包问题的时间复杂度为 $O(n\ast c)$，空间复杂度为 $O(n\ast c)$，其中 $n$ 表示物品的数量，$c$ 表示背包的容量。

/**
 * 动态规划求解0-1背包问题
 * @param w 物品重量
 * @param v 物品价值
 * @param c 背包容量
 * @return 背包能装下的最大价值
 * 时间复杂度：O(n*c)
 * 空间复杂度：O(n*c)
 * 优点：时间复杂度较低，能够求解较大规模的问题
 * 缺点：空间复杂度较高，不适用于数据量较大的问题
 */
func knapsack(w []int, v []int, c int) int {
	n := len(w)
	dp := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, c+1)
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= c; j++ {
			if j < w[i-1] {
				// 背包容量不足，不能装入第i个物品
				dp[i][j] = dp[i-1][j]
			} else {
				// 能装入第i个物品
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1])
			}
		}
	}
	// 返回背包能装下的最大价值
	return dp[n][c]
}

贪心算法

贪心算法是求解0-1背包问题的一种常用算法，其时间复杂度较低，能够求解较大规模的问题。贪心算法的基本思想是每次选择当前最优的解，直到得到最终的解。

贪心算法求解0-1背包问题的时间复杂度为 $O(n\ast log(n))$，空间复杂度为 $O(n)$。

 */
func greedyKnapsack(w []int, v []int, c int) int {
	n := len(w)
	index := make([]int, n)
	for i := 0; i < n; i++ {
		index[i] = i
	}
	temp := make([]int, n)
	for i := 0; i < n; i++ {
		temp[i] = v[i] * w[i]
	}
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if temp[i] < temp[j] {
				t := temp[i]
				temp[i] = temp[j]
				temp[j] = t
				t = index[i]
				index[i] = index[j]
				index[j] = t
			}
		}
	}
	maxValue := 0
	for i := 0; i < n; i++ {
		if w[index[i]] <= c {
			maxValue += v[index[i]]
			c -= w[index[i]]
		} else {
			maxValue += int(float64(v[index[i]])/float64(w[index[i]])*float64(c))
			break
		}
	}
	return maxValue
}

回溯算法

回溯算法是求解0-1背包问题的一种常用算法，其能够求解较小规模的问题。回溯算法的基本思想是搜索所有可能的解，找到最优解。

回溯算法求解0-1背包问题的时间复杂度为 $O(2^n)$，空间复杂度为 $O(n)$。

/**
 * 回溯算法求解0-1背包问题
 * @param w 物品重量
 * @param v 物品价值
 * @param c 背包容量
 * @return 背包能装下的最大价值
 * 时间复杂度：O(2^n)
 * 空间复杂度：O(n)
 * 优点：能够求解较小规模的问题
 * 缺点：时间复杂度较高，不适用于数据量较大的问题
 */
func backtrackKnapsack(w []int, v []int, c int) int {
	n := len(w)
	maxValue := 0
	for i := 0; i < (1 << n); i++ {
		currentWeight := 0
		currentValue := 0
		for j := 0; j < n; j++ {
			if (i & (1 << j)) != 0 {
				currentWeight += w[j]
				currentValue += v[j]
			}
		}
		if currentWeight <= c && currentValue > maxValue {
			maxValue = currentValue
		}
	}
	return maxValue
}

分支定界算法

分支定界算法是求解0-1背包问题的一种常用算法，其能够求解较小规模的问题。分支定界算法的基本思想是搜索所有可能的解，但是在搜索过程中，通过一些限制条件，剪枝掉一些不可能成为最优解的分支，从而减少搜索的时间。

分支定界算法求解0-1背包问题的时间复杂度为 $O(2^n)$，空间复杂度为 $O(n)$。

/**
 * 分支定界算法求解0-1背包问题
 * @param w 物品重量
 * @param v 物品价值
 * @param c 背包容量
 * @return 背包能装下的最大价值
 * 时间复杂度：O(2^n)
 * 空间复杂度：O(n)
 * 优点：能够求解较小规模的问题
 * 缺点：时间复杂度较高，不适用于数据量较大的问题
 */
func branchBoundKnapsack(w []int, v []int, c int) int {
	n := len(w)
	index := make([]int, n)
	for i := 0; i < n; i++ {
		index[i] = i
	}
	temp := make([]int, n)
	for i := 0; i < n; i++ {
		temp[i] = v[i] * w[i]
	}
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if temp[i] < temp[j] {
				t := temp[i]
				temp[i] = temp[j]
				temp[j] = t
				t = index[i]
				index[i] = index[j]
				index[j] = t
			}
		}
	}
	maxValue := 0
	currentValue := 0
	currentWeight := 0
	i := 0
	for i >= 0 {
		if i == n {
			if currentValue > maxValue {
				maxValue = currentValue
			}
			i--
		} else if currentWeight+w[index[i]] <= c {
			currentWeight += w[index[i]]
			currentValue += v[index[i]]
			i++
		} else {
			i--
		}
		if i >= n || i < 0 || index[i] >= n || currentWeight+w[index[i]] > c || currentValue+(c-currentWeight)*v[index[i]]/w[index[i]] <= maxValue {
			i--
		}
	}
	return maxValue
}

算法汇总代码

package main

import (
	"fmt"
	"time"
)

func main() {
	// 物品重量
	w := []int{2, 4, 6, 8, 9, 2, 4, 6, 8, 9, 2, 4, 6, 8, 9, 2, 4, 6, 8, 9}
	// 物品价值
	v := []int{1, 3, 5, 7, 9, 1, 3, 5, 7, 9, 1, 3, 5, 7, 9, 1, 3, 5, 7, 9}
	// 背包容量1
	c1 := 10
	// 背包容量2
	c2 := 100
	start1 := time.Now()
	result1 := knapsack(w, v, c1)
	end1 := time.Now()
	start2 := time.Now()
	result2 := knapsack(w, v, c2)
	end2 := time.Now()
	fmt.Printf("当背包容量为10时，动态规划算法的结果为：%d，执行时间为：%v\n", result1, end1.Sub(start1))
	fmt.Printf("当背包容量为10时，贪心算法的结果为：%d\n", greedyKnapsack(w, v, c1))
	fmt.Printf("当背包容量为10时，回溯算法的结果为：%d\n", backtrackKnapsack(w, v, c1))
	fmt.Printf("当背包容量为10时，分支定界算法的结果为：%d\n", branchBoundKnapsack(w, v, c1))
	fmt.Printf("当背包容量为100时，动态规划算法的结果为：%d，执行时间为：%v\n", result2, end2.Sub(start2))
	fmt.Printf("当背包容量为100时，贪心算法的结果为：%d\n", greedyKnapsack(w, v, c2))
	fmt.Printf("当背包容量为100时，回溯算法的结果为：%d\n", backtrackKnapsack(w, v, c2))
	fmt.Printf("当背包容量为100时，分支定界算法的结果为：%d\n", branchBoundKnapsack(w, v, c2))
}

/**
 * 动态规划求解0-1背包问题
 * @param w 物品重量
 * @param v 物品价值
 * @param c 背包容量
 * @return 背包能装下的最大价值
 * 时间复杂度：O(n*c)
 * 空间复杂度：O(n*c)
 * 优点：时间复杂度较低，能够求解较大规模的问题
 * 缺点：空间复杂度较高，不适用于数据量较大的问题
 */
func knapsack(w []int, v []int, c int) int {
	n := len(w)
	dp := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, c+1)
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= c; j++ {
			if j < w[i-1] {
				// 背包容量不足，不能装入第i个物品
				dp[i][j] = dp[i-1][j]
			} else {
				// 能装入第i个物品
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1])
			}
		}
	}
	// 返回背包能装下的最大价值
	return dp[n][c]
}

/**
 * 贪心算法求解0-1背包问题
 * @param w 物品重量
 * @param v 物品价值
 * @param c 背包容量
 * @return 背包能装下的最大价值
 * 时间复杂度：O(n*log(n))
 * 空间复杂度：O(n)
 * 优点：时间复杂度较低，能够求解较大规模的问题
 * 缺点：不能保证求得的是最优解，只能得到一个近似解
 */
func greedyKnapsack(w []int, v []int, c int) int {
	n := len(w)
	index := make([]int, n)
	for i := 0; i < n; i++ {
		index[i] = i
	}
	temp := make([]int, n)
	for i := 0; i < n; i++ {
		temp[i] = v[i] * w[i]
	}
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if temp[i] < temp[j] {
				t := temp[i]
				temp[i] = temp[j]
				temp[j] = t
				t = index[i]
				index[i] = index[j]
				index[j] = t
			}
		}
	}
	maxValue := 0
	for i := 0; i < n; i++ {
		if w[index[i]] <= c {
			maxValue += v[index[i]]
			c -= w[index[i]]
		} else {
			maxValue += int(float64(v[index[i]])/float64(w[index[i]])*float64(c))
			break
		}
	}
	return maxValue
}

/**
 * 回溯算法求解0-1背包问题
 * @param w 物品重量
 * @param v 物品价值
 * @param c 背包容量
 * @return 背包能装下的最大价值
 * 时间复杂度：O(2^n)
 * 空间复杂度：O(n)
 * 优点：能够求解较小规模的问题
 * 缺点：时间复杂度较高，不适用于数据量较大的问题
 */
func backtrackKnapsack(w []int, v []int, c int) int {
	n := len(w)
	maxValue := 0
	for i := 0; i < (1 << n); i++ {
		currentWeight := 0
		currentValue := 0
		for j := 0; j < n; j++ {
			if (i & (1 << j)) != 0 {
				currentWeight += w[j]
				currentValue += v[j]
			}
		}
		if currentWeight <= c && currentValue > maxValue {
			maxValue = currentValue
		}
	}
	return maxValue
}

/**
 * 分支定界算法求解0-1背包问题
 * @param w 物品重量
 * @param v 物品价值
 * @param c 背包容量
 * @return 背包能装下的最大价值
 * 时间复杂度：O(2^n)
 * 空间复杂度：O(n)
 * 优点：能够求解较小规模的问题
 * 缺点：时间复杂度较高，不适用于数据量较大的问题
 */
func branchBoundKnapsack(w []int, v []int, c int) int {
	n := len(w)
	index := make([]int, n)
	for i := 0; i < n; i++ {
		index[i] = i
	}
	temp := make([]int, n)
	for i := 0; i < n; i++ {
		temp[i] = v[i] * w[i]
	}
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if temp[i] < temp[j] {
				t := temp[i]
				temp[i] = temp[j]
				temp[j] = t
				t = index[i]
				index[i] = index[j]
				index[j] = t
			}
		}
	}
	maxValue := 0
	currentValue := 0
	currentWeight := 0
	i := 0
	for i >= 0 {
		if i == n {
			if currentValue > maxValue {
				maxValue = currentValue
			}
			i--
		} else if currentWeight+w[index[i]] <= c {
			currentWeight += w[index[i]]
			currentValue += v[index[i]]
			i++
		} else {
			i--
		}
		if i >= n || i < 0 || index[i] >= n || currentWeight+w[index[i]] > c || currentValue+(c-currentWeight)*v[index[i]]/w[index[i]] <= maxValue {
			i--
		}
	}
	return maxValue
}