[ACM/算法]01背包问题详解+扩展

01背包问题作为著名的动态规划问题之一,在算法学习中的意义不言而喻。

最近刷到一道题,在01背包问题中有稍微改变。

BeiBaoQuestion

题中不仅要求输出最大概率之和,还要求输出楼盘ID。

动态规划问题

例如输入序列为:

5 10
2 0.2
3 0.3
4 0.44
5 0.55
6 0.6

贪心算法:

第一种解法是贪心算法

  1. 将所有楼盘序列计算出单位概率。
  2. 按照单位概率将序列排序。
  3. 依次从高概率遍历到低概率,从而得到局部最优解。

算法代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def ():
number, fund = input().split(' ')
fund = int(fund)
array = []
max_prob = []
max_value = 0
for i in range(int(number)):
value, prob = input().split(' ')
current_id = i+1
array.append([current_id, int(value), float(prob), float(prob)/float(value)])
print(array)
# 第四位排序
array.sort(key=take_four, reverse=True)
print(array)
for i in array: # 选中最佳可能的资金
max_value += i[1]
if max_value < fund:
max_prob.append([i[0], i[2]])
print('max_prob:', max_prob)
max_prob_value = 0
for i in max_prob:
max_prob_value = i[1] + max_prob_value
print(max_prob_value, [x[0] for x in max_prob])

我们可以得到结果

0.99 [4, 3]

显然这不是我们想要的结果,因为最优解应该为1,2,4 = 1.05才对。

动态规划

寻找最大概率值

使用动态规划的方法解决该问题需要对问题建立转移方程:

  1. 输入楼盘数量为number,总资金为fund

  2. 输入楼盘的数据raw_data.

  3. 定义子问题P(i, v)为在前i个楼盘中挑选总价值不超过v的楼盘,并且每个楼盘只能选择一次,使得最终抽中的总概率最大。我们此时的最优解记作max_prob(i, w),其中1<=i<=number,1<=w<=fund。

  4. 当我们考虑第i个楼盘的时候:

    如果不选择,则总资金容量不变,改为问题P(i-1, w)

    如果选择这个楼盘,则总资金剩余容量变小,改问题为P(i-1, w-wi)

  5. 最优解的问题就是比较3中两个方案哪一个是最佳的:

    max_prob(i,w) = max{max_prob(i-1,w),max_prob(i-1,w-wi)+valuei}

例如输入序列为:

5 10
2 0.2
3 0.3
4 0.44
5 0.55
6 0.6

假设我们一共有10W金钱,楼盘价值分别为2,3,4,5,6。楼盘概率分别为0.2,0.3,0.44,0.55,0.6。

那么我们通过转移方程可以推算出以下表格max_prob:

1552028354656

推算过程:

  1. 建立一个表格,大小为number×fund。

  2. 逐层遍历,按列遍历。

    1. 当资金为1的时候,没有任何房产可以购买。

    2. 当资金为2的时候,可以购买房产1。

    3. 当资金为3的时候,可以购买房产1,但是当遍历到(2,3)的时候,对比

      max{max_prob(i-1,w),max_prob(i-1,w-wi)+valuei}

      其中max_prob(i-1,w) 代表i-1行w列。

      其中max_prob(i-1,w)为0.2,max_prob(i-1,w-wi)+valuei 为0.2-0.2 + 0.3 = 0.3

    4. 经过逐次的遍历,得到最终整个矩阵数据。

算法代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def dynasty():
# ----------------输入数据----------------------
number, fund = input().split(' ')
fund = int(fund)
number = int(number)
max_prob = [[0 for col in range(fund+1)] for row in range(number+1)]
raw_data = []
for i in range(int(number)):
value, prob = input().split(' ')
current_id = i+1
raw_data.append([current_id, int(value), float(prob), float(prob)/float(value)])
# ---------------计算概率分布矩阵-------------------
all_max = 0
for i in range(1, number+1): # 遍历所有的房价,number为房产个数
for j in range(1, fund+1): # 遍历所有总金额,
# print(i, j, raw_data[i-1][1])
if j < raw_data[i-1][1]: # 假定的总金额小于当前房产的价格
max_prob[i][j] = max_prob[i-1][j] # 概率等于之前的
else:
max_prob[i][j] = max(max_prob[i-1][j], (max_prob[i-1][j-raw_data[i-1][1]] + raw_data[i-1][2]))
if max_prob[i][j] > all_max: # 记录概率最大值
all_max = max_prob[i][j]

# ----------------打印概率分布矩阵---------------
print('概率分布矩阵:n', max_prob)
print('all_max_prob:', all_max)
计算楼盘的序列
  1. 定义指针(i,j)倒序遍历表格

  2. 从末尾开始遍历,寻找按顺序排列第一次出现all_max节点,将all_max修改为all_max-raw_data[i][prob]

  3. 当找到第一个星号1.05后移动指针位置到(i-1,j-1),检测当前值是否为第一次出现的all_max,如果是,标记为星,并重复2步骤,直到遍历到(0,0)

  4. 输出所有标记星所在的行即为楼盘序列。

    1552030438642

算法代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# ----------------从表中推出楼盘列表--------------
id_list = []
# id_list.append(max_id)
# 反向查找关键节点
j = fund # 定义列位置
i = number # 定义行位置
while i != 0 and j != 0: # 从max_prob表右下位置开始,逆序遍历
# print('all_max:', all_max)
print('当前遍历的节点i,j,prob:', i, j, max_prob[i][j])
# print('value:', int(max_prob[i][j]))
# print('value_(i,j-1):', int(max_prob[i][j-1]))
# 如果同行上一列的的概率值仍然为最大,则切换到上一列
if max_prob[i][j-1] == all_max:
# print('j = j-1')
j = j-1
# 如果同列上一行的的概率值仍然为最大,则切换到上一行
elif max_prob[i - 1][j] == all_max:
# print('i = i-1')
i = i-1
# 处于拐点,可能是一个关键点。
else:
# print('test', int(max_prob[i][j]), int(all_max - raw_data[i-1][2]))
# 如果当前概率等于最大的概率,则是关键点
if max_prob[i][j] == all_max:
id_list.append(raw_data[i-1][0]) # 保存当前楼盘的id
all_max = all_max - raw_data[i-1][2] # 转换当前最大概率,寻找下一个关键节点
print('----当前楼盘是关键点之一:', i, '下一个节点prob为:', all_max)
i = i-1
j = j-1
print(id_list)

算法源码点击 这里

引用:

https://blog.csdn.net/huanghaocs/article/details/77920358

https://zhuanlan.zhihu.com/p/30959069