这篇文章给大家聊聊关于01 Leetcode 416的背包问题及解决方案，以及对应的知识点，希望对各位有所帮助，不要忘了收藏本站哦。

有N件物品和一个容量为V的背包。第i件物品中最多有n件物品可用，每件物品的体积为c，值为w。找出哪些物品可以放入背包中，使这些物品的总体积不超过背包容量且总价值最大。 1.2 解决问题的思路

回答这个问题最简单的方法就是穷举法。另一种方法是动态规划，按顺序解决子问题。

穷举法：最基本的思想就是尝试各种物品的组合，然后选择背包中价值最大的组合。通过这个想法，每个物品都有两种选择：放入背包或不放入背包。组合数为2^n。时间复杂度为o(2^n)。如此指数级的时间复杂度在工程上显然是不可取的。

动态规划：这道题，可以考虑用动态规划方法先解决局部子问题，然后再解决最终问题。动态规划问题的核心是寻找动态规划方程，动态规划方程用于将问题划分为子问题。下面是分析思路。

一个容量为v的背包可以分为两个容量为v1 + v2=v的背包组合。这两个背包组合的值之和可能是背包最大值的潜在答案之一依次将容量为v、v1、v2分解为小容量的背包，我们就可以逆向推导出容量为v的背包问题的解。那么容量为v的背包如何划分呢？

可以考虑依次取出第i个物品（i从1到n遍历），它的体积为ci。此时选择是否将物品放入背包。那么就有两种可能，把该item放入或者不放入This item。如果放入该物品，需要保证背包容量足够。如果不放入该物品，则背包当前的最大值将与取出第i-1 件物品时相同。

对比这两种情况得到的值，如果背包中放置的物品价值较大且容量足够，那么当放置第i个物品时，背包的最优解是放置第i个物品。否则，取出第i 件物品的最优解为相当于取出第i-1 件物品时的情况。

当计算放置第i个物品时背包的最大值时，需要知道容量为v – ci的子问题的背包的最大值。

这个问题的划分思路是，在计算第i项时，计算背包容量为1~v时的最优解。当最终计算第n项时，容量为v的最优解就是原问题。最终解决方案。动态规划的方程如下：

动态规划方程

上式中，dp[i][j]表示前i件物品，背包容量为j时背包问题的最佳解，其中0=i n，0=j=v。ci为物品i的体积， v[i] 是第i 项的值。

代码实现如下：

//golang实现//动态编程func Backpack(capacities []int, values[]int,capacity int) int { dp :=make([][]int, len(values)) for i :=0;我的长度（值）； i++ { dp[i]=make([]int,capacity+1) } //当只有一项时，背包问题的dp[0] 解对于i :=capacity[0];我的能力； i++ { dp[0][i]=值[0] } 对于i :=1；我的长度（值）； i++ { for j :=0;j=容量； j++ { 如果j 容量[i] || dp[ i-1][j]=值[i] + dp[i][j – 容量[i]] { dp[i][j]=dp[i-1][j] }else { dp[ i] [j]=值[i] + dp[i][j – 容量[i]] } } } 返回dp[len(values)-1][容量]}

2. leetcode 416 Partition Equal Subset Sum 及题解

背包问题是一个经典问题，其解题思路已被应用到很多问题中。这是面试中经常被问到的问题。其中Leetcode 416的解决思路是背包问题。事实上，leetcode 416是一个更简单的背包问题。

2.1 主题描述

给定一个仅包含正整数的非空数组，找出该数组是否可以划分为两个子集，使得两个子集中的元素之和相等。

注：

每个数组元素不会超过100。数组大小不会超过200。示例1:

输入： [1, 5, 11, 5]输出： true解释：数组可以分为[1, 5, 5] 和[11]。示例2:

输入： [1, 2, 3, 5]输出： false解释：数组无法划分为等和子集。题目的主要思想是判断数组是否可以分为两个子数组，并且两个子数组的和相等。的。

2.2 问题解决

这个问题和背包问题是一样的。可以使用穷举法列出所有的组合，但时间复杂度太高，在工程上不可行。另一种方法是动态规划，它可以分解为子问题。先解决子问题，然后逐步解决原问题。

其实这个问题可以通过将背包容量设置为sum/2来解决，每个数字的大小作为物品的体积。这个问题的最优解不需要考虑物品的价值，而是考虑背包能否装满。事实上它比背包问题更简单。它只有一个体积，子问题是前i个物品的组合能否恰好装满容量为0~sum/2的背包。

设dp[i]为容量为i的背包能否被前j个物品的组合恰好装满，nums[j]为物品的体积。那么动态规划方程就是：

dp[i]=dp[i-j]

下面是实现：的代码

//golang 实现func canPartition(nums []int) bool { var sum int for _, num :=range nums { sum +=num } //sum/2 有小数，nums 都是正数，显然不能用if sum % 2==1 { return false } sum=sum/2 //目标dp :=make([]bool, sum+1) dp[0]=true for _, v :=range nums { //添加Volume 为v 的数量后，重新判断容量为v ~ sum 的背包是否可以装满j :=sum; j 0; j– { 如果j=v dp[j-v] { dp[j]=true } } } 返回dp[sum]}

3.1 其他

0-1背包问题是背包问题之一。背包问题可以分为三类，包括： 0-1背包问题、完全背包问题和多个背包问题。它们是动态规划的经典问题。

背包问题可以出现在现实世界各个领域的决策过程中，比如资产证券化、投资组合、投资选择等。背包问题除了频繁出现在采访中之外，也是一个值得探讨的问题。人们对它的研究已经有1个多世纪了。

3.2 参考文献

1. 0-1背包问题[https://www.jianshu.com/p/a66d5ce49df5]