01背包问题简单思路

发布时间:2024年01月15日
问题描述:
	给你一个体积为5的背包,要求将下列物品中的一个或多个装入背包,使背包能有最大价值(每个物品有且仅有一个)。
	物品1:体积1,价值2
	物品2:体积2,价值4
	物品3:体积3,价值4
	物品4:体积4,价值5

文章目录




物品编号为0表示该物品大小为0,价值为0,用来辅助的。
物品编号\背包体积012345
0
1a
2
3b
4

表格中的a表示:当背包体积为1时,且只有两个物品供选择时(物品0和物品1),背包的最大价值

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






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

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

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

物品编号\背包体积012345
0000000
10
20
30
40




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

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

  • 情况1:若最大编号物品的体积大于当前背包体积
最大编号物品肯定是放不进背包的,于是我们就要去找,同体积背包下,排除最大编号物品,背包的最大价值。
  • 情况2:若最大编号物品的体积小于等于当前背包体积
如果是这种情况,我们又要将其细分为两种情况:
	- 不装入最大编号物品
			如果不装入,那么跟情况1一样,同体积背包下,排除最大编号物品,背包的最大价值
	- 装入最大编号物品
			如果装入,那么就去找减去该物品体积后,背包剩余体积的最大价值。(找背包剩余体积最大价值时,一定要排除最大编号物品,因为它已经装入背包了)。然后将该物品价值与背包剩余体积的最大价值相加。
	- 然后将装入与不装入的背包价值相比较,取较大者

下面来逐步填写





物品编号\背包体积012345
0000000
10
20
30
40

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

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





物品编号\背包体积012345
0000000
102
20
30
40

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

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

然后按照此规则,将这一行填完:





物品编号\背包体积012345
0000000
1022222
20
30
40

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

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





物品编号\背包体积012345
0000000
1022222
202
30
40

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

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





物品编号\背包体积012345
0000000
1022222
2024
30
40

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

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





物品编号\背包体积012345
0000000
1022222
20246
30
40

然后按照此规则,将这一行填完:





物品编号\背包体积012345
0000000
1022222
2024666
30
40

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

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





物品编号\背包体积012345
0000000
1022222
2024666
302
40

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

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





物品编号\背包体积012345
0000000
1022222
2024666
3024
40

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

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





物品编号\背包体积012345
0000000
1022222
2024666
30246
40

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

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





物品编号\背包体积012345
0000000
1022222
2024666
302466
40

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

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





物品编号\背包体积012345
0000000
1022222
2024666
3024668
40

然后按照此规则,将最后一行填完:





物品编号\背包体积012345
0000000
1022222
2024666
3024668
4024668

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




代码

# 背包大小
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])
文章来源:https://blog.csdn.net/weixin_62917800/article/details/135611971
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。