完全背包问题简单思路

发布时间:2024年01月22日

01背包简单理解

问题描述:
	给你一个体积为10的背包,要求将下列物品中的一个或多个装入背包,使背包能有最大价值(每个物品有无限个)
	物品1:体积2,价值1
	物品2:体积3,价值3
	物品3:体积4,价值5
	物品4:体积7,价值9

文章目录

且看下面表格理解:

物品编号\体积012345678910
000000000000
10a
20
30b
40
说明:
	- 编号为0的物品价值也为0,所以第一行全为0
	- 当背包体积为0时,一个物品也装不下,所以第一列全为0
	- a点表示当背包体积为2时,只有物品0和物品1(当前物品)可装入背包,此时背包的最大价值
	- b点表示当背包体积为7时,有物品0、物品1、物品2、物品3(当前物品)可装入背包,此时背包的最大价值
完全背包求最大价值步骤规则:
	- 每一个格子都默认继承该列的上一行的那个格子的值,例如,a点(1,2)的值就默认继承(0,2)的值
	- 判断当前物品(相当于每个格子对应的行,对应的行又代表物品编号,所以也就叫做当前物品了)是否能装入背包中:
		- 若不能装入,就继承
		- 若能装入,比较“继承的值”和“当前物品的价值+背包体积减去当前物品体积所剩余的体积的最大价值”
			- 与01背包不同的是,找剩余背包体积的最大价值时,是去该行寻找(因为完全背包中,每个物品有无限个,
			而01背包中,每个物品有且仅有一个)

下面来一步一步找出每个格子的值

初始化表格(物品编号右边数字分别表示物品的体积和价值):

物品编号\体积012345678910
000000000000
1(2,1)0
2(3,3)0
3(4,5)0
4(7,9)0



判断(1,1)点:

背包体积为1,当前物品体积为2,不能装入,继承(0,1)

物品编号\体积012345678910
000000000000
1(2,1)00
2(3,3)0
3(4,5)0
4(7,9)0



判断(1,2)点:

背包体积为2,当前物品体积为2,能装入

装入后背包剩余体积为0,剩余背包体积最大价值应去找(1,0)

比较继承的值和当前物品价值+剩余背包体积最大价值:0 < 1 + 0

物品编号\体积012345678910
000000000000
1(2,1)001
2(3,3)0
3(4,5)0
4(7,9)0



判断(1,3)点:

背包体积为3,当前物品体积为2,能装入

装入后背包剩余体积为0,剩余背包体积最大价值应去找(1,1)

比较继承的值和当前物品价值+剩余背包体积最大价值:0 < 1 + 0

物品编号\体积012345678910
000000000000
1(2,1)0011
2(3,3)0
3(4,5)0
4(7,9)0



判断(1,4)点:

背包体积为4,当前物品体积为2,能装入

装入后背包剩余体积为2,剩余背包体积最大价值应去找(1,2)

比较继承的值和当前物品价值+剩余背包体积最大价值:0 < 1 + 1

此时背包就装了两个物品1了
物品编号\体积012345678910
000000000000
1(2,1)00112
2(3,3)0
3(4,5)0
4(7,9)0



第一行就按照这样的规则来判断…下面直接给出

物品编号\体积012345678910
000000000000
1(2,1)00112233445
2(3,3)0
3(4,5)0
4(7,9)0



判断(2,1)点:

背包体积为1,当前物品体积为3,不能装入,继承(1,1)

物品编号\体积012345678910
000000000000
1(2,1)00112233445
2(3,3)00
3(4,5)0
4(7,9)0



判断(2,2)点:

背包体积为2,当前物品体积为3,不能装入,继承(1,2)

物品编号\体积012345678910
000000000000
1(2,1)00112233445
2(3,3)001
3(4,5)0
4(7,9)0



判断(2,3)点:

背包体积为3,当前物品体积为3,能装入

装入后背包剩余体积为0,剩余背包体积最大价值应去找(2,0)

比较继承的值和当前物品价值+剩余背包体积最大价值:0 < 3 + 0

物品编号\体积012345678910
000000000000
1(2,1)00112233445
2(3,3)0013
3(4,5)0
4(7,9)0



判断(2,4)点:

背包体积为4,当前物品体积为3,能装入

装入后背包剩余体积为1,剩余背包体积最大价值应去找(2,1)

比较继承的值和当前物品价值+剩余背包体积最大价值:0 < 3 + 0

物品编号\体积012345678910
000000000000
1(2,1)00112233445
2(3,3)00133
3(4,5)0
4(7,9)0



判断(2,5)点:

背包体积为5,当前物品体积为3,能装入

装入后背包剩余体积为2,剩余背包体积最大价值应去找(2,2)

比较继承的值和当前物品价值+剩余背包体积最大价值:0 < 3 + 1

物品编号\体积012345678910
000000000000
1(2,1)00112233445
2(3,3)001334
3(4,5)0
4(7,9)0



判断(2,6)点:

背包体积为6,当前物品体积为3,能装入

装入后背包剩余体积为3,剩余背包体积最大价值应去找(2,3)

比较继承的值和当前物品价值+剩余背包体积最大价值:0 < 3 + 3

物品编号\体积012345678910
000000000000
1(2,1)00112233445
2(3,3)0013346
3(4,5)0
4(7,9)0



就按照这样的规则一直填写…

物品编号\体积012345678910
000000000000
1(2,1)00112233445
2(3,3)00133466799
3(4,5)00135568101011
4(7,9)00135569101012

代码

# 存储每个物品的体积和价值。objects[0][0]表示物品1的体积,objects[0][1]表示物品1的价值
objects = [[2, 1], [3, 3], [4, 5], [7, 9]]

def CompeleteBag(objects, bagSize):
    # 表格的高度(相当于y轴),加1是因为用了物品0作为假设
    height = len(objects) + 1
    # 表格的宽度(相当于x轴),加1是因为还有背包体积为0作为假设
    width = bagSize + 1

    # 初始化表格,将表格中的每个格子置零,其目的是为了让第一行和第一列的格子置零
    dp = [[0] * width for i in range(0, height)]

    # 这里两个循环都从1开始是跳过第一行和第一列的格子
    # i代表的是物品的标号
    for i in range(1, height):
        # j代表的是背包的体积
        for j in range(1, width):
            # 默认继承该列上一行的格子的值
            dp[i][j] = dp[i - 1][j]

            # 定义背包剩余体积最大价值
            surplusValue = 0

            # 判断当前物品是否能放入,不能放入自然就继承
            # 若能放入,就比较(继承的值)和(当前物品价值+背包体积减去该物品体积剩余体积的最大价值)
            # 注意:剩余体积最大价值应该在当前物品这一行去找,(01背包是去上一行物品找)

            # 如果当前物品体积小于等于背包体积,也就是此时背包能放下当前物品
            if objects[i - 1][0] <= j:
                # 获取当前物品的价值
                value = objects[i - 1][1]

                # 在当前物品行找到剩余背包体积的最大价值
                surplusValue = dp[i][j - objects[i - 1][0]]

                # 比较继承的值和放入当前物品后背包的最大价值,若大于继承的值,就用value+surplusValue代替
                if dp[i][j] < value + surplusValue:
                    dp[i][j] = value + surplusValue
    return dp
文章来源:https://blog.csdn.net/weixin_62917800/article/details/135751411
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。