背包问题(三)-多重背包(简单)-史上最详细解答
背包问题(三)-多重背包(简单)-史上最详细解答1. 题目2. 分析2.1 状态表示2.2 状态计算3. 实现4. 优化4.1 去除k循环(时间复杂度优化)4.2 转化成一维数组解法(空间复杂度优化)5. 测试参考链接进阶:多重背包(中等)1. 题目问题描述:有n件物品和容量为m的背包,给出i件物品的重量以及价值value,还有数量number,求解让装入背包的物品重量不超过背包容量W,且价值V最
背包问题(三)-多重背包(简单)-史上最详细解答
1. 题目
- 问题描述:有n件物品和容量为m的背包,给出i件物品的重量以及价值value,还有数量number,求解让装入背包的物品重量不超过背包容量W,且价值V最大 。
- 特点 :它与完全背包有类似点,特点是每个物品都有了一定的数量。
2. 分析
2.1 状态表示
一般用dp数组来计算动态规划问题,从以下两个方面对动态规划问题进行表示
-
集合
- v集合:物品价值
- w集合:物品重量
- 从前i个物品里面选取总重量<=j的所有物品的选法,与完全背包的区别在于,每一种物品是有个数限制的,不能无限选择
- 因此此处需要多一个num集合:每个物品的数量
-
属性
- max
- min
- count
本题属性是属于求最大价值,为max
2.2 状态计算
对于多重背包的问题,遵从01背包的策略,是选择放或者不放两个状态,但是每一种物品可以放最多num[i]个,因此可以转换为:实际上我们对于一个物品的选择就是放多少个的问题,最多放num[i]个的问题:
我们假设一种物品选择k个(除了背包本身重量限制,k还受到每一类物品数量num[i]的限制),则k的范围为:0 < k && k * w[i] <= j && k <= num[i]
- 选择放进去
如果选择放进去,还需要考虑放进去多少个,即:
1, 2, 3, ···, k-1, k个且(0 < k && k * w[i] <= j && k <= num[i])
表示在上一个物品的状态的时候,我的当前背包重量j需要减去当前k个物品的重量k*w[i],并且整个背包的价值需要加上当前k个物品的价值k*v[i],则状态方程为:
# 0 < k && k * w[i] <= j && k <= num[i]
dp[i][j] = dp[i-1][j-k*w[i]] + k*v[i]
- 选择不放进去
实际上如果选择不放进去的时候,表示放进去的是0个,需要减去的kw[i]和需要加上的kv[i]都为0选择不放进去的状态方程则为:
# dp[i][j] = dp[i-1][j-0*w[i]] + 0*v[i]
dp[i][j] = dp[i-1][j]
由此我们可以得到状态转移方程:
# 0 < k && k * w[i] <= j && k <= num[i]
dp[i][j] = max(dp[i-1][j-k*w[i]] + k*v[i], dp[i-1][j])
3. 实现
根据上面的状态转移方程我们可以得到多重背包的解法:
def _multiple_two_dim_k_function(data, number, total_weight):
"""
状态转移方程:
dp[i][j] = max(dp[i-1][j-k*w[i]] + k*v[i], dp[i-1][j]) (0<k<=num[i])
:param data:
:param number:
:param total_weight:
:return:
"""
# 由于数据从1开始计算因此+1
row = number + 1
col = total_weight + 1
# dp = [[0] * col for _ in range(row)]
dp = np.array([0] * (row * col)).reshape(row, col)
for i in range(1, row):
if i == len(data):
break
item = data[i]
v = item.get("value")
w = item.get("weight")
num = item.get("number")
for j in range(1, col):
for k in range(1, num + 1): # 最多只能到num[i]
if j >= k * w:
input_val = dp[i - 1][j - k * w] + k * v
noput_val = dp[i - 1][j]
dp[i][j] = max(input_val, noput_val)
else:
dp[i][j] = dp[i - 1][j]
break # 如果k * w >= j了这个循环就没必要继续了
return dp[number - 1][total_weight]
4. 优化
4.1 去除k循环(时间复杂度优化)
此处不能够去除K循环!!
在完全背包算法中我们用简单的替换,可以把状态转移方程中的k给去除,原因是每一个物品的k的范围是固定的,我们可以把k当做公因式进行提取。
而在多重背包当中,因为k不仅与重量j有关,还与当前物品的最多可以选择的数量有关,因此k是不能够被当做公因式处理,也就不能够用完全背包的化简方式进行去除。
4.2 转化成一维数组解法(空间复杂度优化)
和01背包的优化逻辑一样,i这个变量其实就是表示“第i个”的一个递增序列,实际的这个背包的当前的状态只有重量(w)和价值(v)
根据刚才的状态方程:
# 不放进去
dp[i][j]=dp[i-1][j]
# 放进去
dp[i][j]=dp[i-1][j-k*w[i]] + k*v[i]
观察两个状态方程,可以看到对于背包重量的状态j是与i无关,因此可以把上述方程简化为:
# 不放进去时候,重量不变,价值不变
dp[j] = dp[j]
# 放进去的时候,背包重量和价值的变化
dp[j] = dp[j-k*w[i]] + k*v[i]
因此可以得到状态转移方程为:
# 0 < k & k*w[i] <= j && k <= num[i]
dp[j] = max(dp[j-k*w[i]] + k*v[i], dp[j])
根据上述的状态转移方程来实现代码:
def _multiple_one_dim_k_function(data, number, total_weight):
"""
状态转移方程:
空间复杂度优化,一维数组实现法
dp[j] = max(dp[j-k*w[i]] + k*v[i], dp[j]) (0 < k && k * w[i] <= j && k <= num[i])
:param data:
:param number:
:param total_weight:
:return:
"""
# 由于数据从1开始计算因此+1
row = number + 1
col = total_weight + 1
# dp = [[0] * col for _ in range(row)]
dp = np.array([0] * col)
for i in range(1, row):
if i == len(data):
break
item = data[i]
v = item.get("value")
w = item.get("weight")
num = item.get("number")
for j in range(col, w, -1):
for k in range(1, num + 1):
if j >= k * w:
dp[j] = max(dp[j - k * w] + k * v, dp[j])
return dp[total_weight]
此处为何与01背包【1】相同,和完全背包【2】不同?,此处又是逆序列遍历j
首先我们观察优化后和优化前的状态转移方程:
# 0 < k && k * w[i] <= j && k <= num[i]
# 优化之前
dp[i][j] = max(dp[i-1][j-k*w[i]] + k*v[i], dp[i-1][j])
# 优化之后
dp[j] = max(dp[j-k*w[i]] + k*v[i], dp[j])
因此实际上优化后的状态转移方程是:
dp[j](第i轮的新值) = max(dp[j-k*w[i]] + k*v[i](第i-1轮的旧值), dp[j](第i-1轮的旧值))
对比01背包的状态转移方程:
dp[j](第i轮的新值) = max(dp[j-w[i]] + v[i](第i-1轮的旧值), dp[j](第i-1轮的旧值))
由状态转移方程可以看出来,多重背包和01背包都需要保证每一次与第i轮比较的数据都是第第i-1轮的旧数据。
原因是j-k*w[i]是做减法的,而这个j又是数组的下标,做减法之后就表示是之前的数据。因此此处逆序遍历,数据才能保证是第i轮更新的数据与第i-1轮的旧数据进行比较。
5. 测试
我们给出01背包的测试数据
{
"things_num": 10,
"items": [{
"value": 7,
"number": 5,
"weight": 1
}, {
"value": 13,
"number": 2,
"weight": 4
}, {
"value": 18,
"number": 1,
"weight": 1
}, {
"value": 5,
"number": 1,
"weight": 7
}, {
"value": 20,
"number": 3,
"weight": 10
}, {
"value": 19,
"number": 1,
"weight": 9
}, {
"value": 6,
"number": 5,
"weight": 10
}, {
"value": 12,
"number": 4,
"weight": 9
}, {
"value": 8,
"number": 1,
"weight": 3
}, {
"value": 10,
"number": 4,
"weight": 6
}],
"total_weight": 37
}
输出:
92
参考链接
【1】01背包详解:https://blog.csdn.net/aninstein/article/details/108061603
【2】完全背包详解:https://blog.csdn.net/aninstein/article/details/108091495
进阶:多重背包(中等)
![Logo](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)