01背包问题简单思路

问题描述：
	给你一个体积为5的背包，要求将下列物品中的一个或多个装入背包，使背包能有最大价值（每个物品有且仅有一个）。
	物品1:体积1，价值2
	物品2:体积2，价值4
	物品3:体积3，价值4
	物品4:体积4，价值5

物品编号为0表示该物品大小为0，价值为0，用来辅助的。

物品编号\背包体积	0	1	2	3	4	5
0
1		a
2
3					b
4

表格中的a表示：当背包体积为1时，且只有两个物品供选择时（物品0和物品1），背包的最大价值

表格中的b表示：当背包体积为4时，且只有四个物品供选择时（物品0、物品1、物品2、物品3），背包的最大价值






知道这个表格的意义之后我们就逐个来填写。首先，

第一行全为0：因为不管背包体积有多大，只有物品0可供选择

第一列全为0：因为不管有多少个物品可以选择，背包的体积始终为0

物品编号\背包体积	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0
2	0
3	0
4	0

然后就按顺序从左到右，从上到下的顺序填写。

填写的过程中需要考虑两种情况（与当前所能选择最大编号物品有关）：

• 情况1：若最大编号物品的体积大于当前背包体积

最大编号物品肯定是放不进背包的，于是我们就要去找，同体积背包下，排除最大编号物品，背包的最大价值。

• 情况2：若最大编号物品的体积小于等于当前背包体积

如果是这种情况，我们又要将其细分为两种情况：
	- 不装入最大编号物品
			如果不装入，那么跟情况1一样，同体积背包下，排除最大编号物品，背包的最大价值
	- 装入最大编号物品
			如果装入，那么就去找减去该物品体积后，背包剩余体积的最大价值。（找背包剩余体积最大价值时，一定要排除最大编号物品，因为它已经装入背包了）。然后将该物品价值与背包剩余体积的最大价值相加。
	- 然后将装入与不装入的背包价值相比较，取较大者

下面来逐步填写

物品编号\背包体积	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0
2	0
3	0
4	0

当背包体积为1，最大编号物品为1时，物品体积<=背包体积：

• noInputValue：不装入物品1，找同背包体积下，排除物品1，背包的最大价值，那么对应着表格中的（0,1），于是noInputValue=0
• InputValue：装入物品1，减去它的体积，背包剩余体积为0，排除物品1，背包剩余体积最大价值的位置就在（0,0），InputValue=物品价值+背包剩余体积最大价值=2+0=2
• noInputValue < InputValue：将大的值填入（1,1）
  
  
  
  
  
  

物品编号\背包体积	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	2
2	0
3	0
4	0

当背包体积为2，最大编号物品为1时，物品体积<=背包体积：

• noInputValue：不装入物品1，找同背包体积下，排除物品1，背包的最大价值，那么对应着表格中的（0,2），于是noInputValue=0
• InputValue：装入物品1，减去它的体积，背包剩余体积为1，排除物品1，背包剩余体积最大价值的位置就在（0,1），InputValue=物品价值+背包剩余体积最大价值=2+0=2
• noInputValue < InputValue：将大的值填入（1,2）

然后按照此规则，将这一行填完：

物品编号\背包体积	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	2	2	2	2	2
2	0
3	0
4	0

当背包体积为1，最大编号物品为2时，物品体积>背包体积：

• Value：不装入物品2，找同背包体积下，排除物品2，背包的最大价值，那么对应着表格中的（1,1），于是Value=2，将2填入（2,1）
  
  
  
  
  
  

物品编号\背包体积	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	2	2	2	2	2
2	0	2
3	0
4	0

当背包体积为2，最大编号物品为2时，物品体积<=背包体积：

• noInputValue：不装入物品2，找同背包体积下，排除物品2，背包的最大价值，那么对应着表格中的（1,2），于是noInputValue=2
• InputValue：装入物品2，减去它的体积，背包剩余体积为0，排除物品2，背包剩余体积最大价值的位置就在（1,0），InputValue=物品价值+背包剩余体积最大价值=4+0=4
• noInputValue < InputValue：将大的值填入（2,2）
  
  
  
  
  
  

物品编号\背包体积	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	2	2	2	2	2
2	0	2	4
3	0
4	0

当背包体积为3，最大编号物品为2时，物品体积<=背包体积：

• noInputValue：不装入物品2，找同背包体积下，排除物品2，背包的最大价值，那么对应着表格中的（1,3），于是noInputValue=2
• InputValue：装入物品2，减去它的体积，背包剩余体积为1，排除物品2，背包剩余体积最大价值的位置就在（1,1），InputValue=物品价值+背包剩余体积最大价值=4+2=6
• noInputValue < InputValue：将大的值填入（2,3）
  
  
  
  
  
  

物品编号\背包体积	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	2	2	2	2	2
2	0	2	4	6
3	0
4	0

然后按照此规则，将这一行填完：

物品编号\背包体积	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	2	2	2	2	2
2	0	2	4	6	6	6
3	0
4	0

当背包体积为1，最大编号物品为3时，物品体积>背包体积：

• Value：不装入物品3，找同背包体积下，排除物品3，背包的最大价值，那么对应着表格中的（2,1），于是Value=2，将2填入（3,1）
  
  
  
  
  
  

物品编号\背包体积	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	2	2	2	2	2
2	0	2	4	6	6	6
3	0	2
4	0

当背包体积为2，最大编号物品为3时，物品体积>背包体积：

• Value：不装入物品3，找同背包体积下，排除物品3，背包的最大价值，那么对应着表格中的（2,2），于是Value=4，将4填入（3,2）
  
  
  
  
  
  

物品编号\背包体积	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	2	2	2	2	2
2	0	2	4	6	6	6
3	0	2	4
4	0

当背包体积为3，最大编号物品为3时，物品体积<=背包体积：

• noInputValue：不装入物品3，找同背包体积下，排除物品3，背包的最大价值，那么对应着表格中的（2,3），于是noInputValue=6
• InputValue：装入物品3，减去它的体积，背包剩余体积为0，排除物品3，背包剩余体积最大价值的位置就在（2,0），InputValue=物品价值+背包剩余体积最大价值=4+0=4
• noInputValue > InputValue：将大的值填入（3,3）
  
  
  
  
  
  

物品编号\背包体积	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	2	2	2	2	2
2	0	2	4	6	6	6
3	0	2	4	6
4	0

当背包体积为4，最大编号物品为3时，物品体积<=背包体积：

• noInputValue：不装入物品3，找同背包体积下，排除物品3，背包的最大价值，那么对应着表格中的（2,4），于是noInputValue=6
• InputValue：装入物品3，减去它的体积，背包剩余体积为1，排除物品3，背包剩余体积最大价值的位置就在（2,1），InputValue=物品价值+背包剩余体积最大价值=4+2=6
• noInputValue > InputValue：将大的值填入（3,4）
  
  
  
  
  
  

物品编号\背包体积	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	2	2	2	2	2
2	0	2	4	6	6	6
3	0	2	4	6	6
4	0

当背包体积为5，最大编号物品为3时，物品体积<=背包体积：

• noInputValue：不装入物品3，找同背包体积下，排除物品3，背包的最大价值，那么对应着表格中的（2,5），于是noInputValue=6
• InputValue：装入物品3，减去它的体积，背包剩余体积为2，排除物品3，背包剩余体积最大价值的位置就在（2,2），InputValue=物品价值+背包剩余体积最大价值=4+4=8
• noInputValue > InputValue：将大的值填入（3,5）
  
  
  
  
  
  

物品编号\背包体积	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	2	2	2	2	2
2	0	2	4	6	6	6
3	0	2	4	6	6	8
4	0

然后按照此规则，将最后一行填完：

物品编号\背包体积	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	2	2	2	2	2
2	0	2	4	6	6	6
3	0	2	4	6	6	8
4	0	2	4	6	6	8

至此结束。只要按照前面说的规则来，就很好理解。

代码

# 背包大小
bagSize = 5

# 存放每个物品的体积和价值，objects[0][0]表示物品1的体积，objects[0][1]表示物品1的价值
objects = [[1, 2], [2, 4], [3, 4], [4, 6]]


def ZeroOneBags(bagSize, objects):
    """

    :param bagSize: 背包最大体积
    :param objects: 物品的体积和价值数组
    :return: 返回最大价值表格
    """
    # 初始化表格，每一个格子都为0，主要是为了让第一行和第一列的格子为0
    maxValueList = [[0] * (bagSize + 1) for i in range(0, len(objects) + 1)]
    # i表示物品编号，从物品1开始
    for i in range(1, len(maxValueList)):
        # j表示假设体积为j的背包，从体积为1开始
        for j in range(1, len(maxValueList[0])):
            # 1. 如果最大编号物品的体积大于当前背包体积
            if objects[i - 1][0] > j:
                # 不装入该物品，直接找排除该物品，背包的最大价值填入
                maxValueList[i][j] = maxValueList[i - 1][j]
                continue

            # 2. 如果最大编号物品的体积小于或等于当前背包体积，分两种情况
            # 2.1 将此物品放入背包，然后计算能产生的最大价值
            # 2.1.1 得到该物品体积和价值
            objVol, objValue = objects[i - 1][0], objects[i - 1][1]
            # 2.1.2 计算背包剩余体积所能产生的最大价值
            surplusValue = maxValueList[i - 1][j - objVol]
            # 2.1.3 计算放入该物品所能产生的总价值
            inputValue = objValue + surplusValue

            # 2.2 不将此物品放入背包，排除该物品，找同体积下背包的最大价值
            noInputValue = maxValueList[i - 1][j]

            # 2.3 比较两者，取较大值
            maxValueList[i][j] = inputValue if inputValue > noInputValue else noInputValue

    return maxValueList

maxValueList = ZeroOneBags(bagSize, objects)
# 打印表格
print(maxValueList)
# 打印背包最大价值
print(maxValueList[-1][-1])