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

算法实现说明

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

0-1背包问题说明

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

有一个容量为 CCC 的背包，和 nnn 个物品，每个物品有重量 wiw_iwi​ 和价值 viv_ivi​，现在需要从这 nnn 个物品中选择一些物品放入背包中，使得这些物品的总重量不超过 CCC，且这些物品的总价值最大。

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

动态规划算法

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

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

/*** 动态规划求解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∗log(n))O(n*log(n))O(n∗log(n))，空间复杂度为 O(n)O(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] = tt = index[i]index[i] = index[j]index[j] = t}}}maxValue := 0for 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(2n)O(2^n)O(2n)，空间复杂度为 O(n)O(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 := 0for i := 0; i < (1 << n); i++ {currentWeight := 0currentValue := 0for 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(2n)O(2^n)O(2n)，空间复杂度为 O(n)O(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] = tt = index[i]index[i] = index[j]index[j] = t}}}maxValue := 0currentValue := 0currentWeight := 0i := 0for 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 mainimport ("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}// 背包容量1c1 := 10// 背包容量2c2 := 100start1 := 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] = tt = index[i]index[i] = index[j]index[j] = t}}}maxValue := 0for 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 := 0for i := 0; i < (1 << n); i++ {currentWeight := 0currentValue := 0for 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] = tt = index[i]index[i] = index[j]index[j] = t}}}maxValue := 0currentValue := 0currentWeight := 0i := 0for 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
}