python - 如何处理以下贪婪/动态问题?
问题描述
我必须检查是否可以从给定数字中得到总和>严格大于给定总和
例如:
如果给定的总和是 9 并且给定的数字是 [3,5,7] 那么正确答案是 1*3 +1*7=10>9 所以输出应该是 [1,0,1]
示例2:
如果给定的总和为 13 且数字为 [1,3,5],则正确答案为 0*1+3*3+1*5=14>13 但 9*1+0*3+5=14 >错误所以正确的输出是 [0,3,1] 如何解决这个问题
解决方案
可以使用无界背包算法的一个版本来获得解决方案。
这里我们从Python Unbound Knapsack修改代码
修改有两个目标:
最小化数组中使用的值的计数
创建小于限制的最大总和(即给定总和 + 1)
def knapsack_unbounded_dp(arr, C):
C += 1 # actual limit
# Form index value pairs (to keep track of the original indexes after sorting)
items = [(i, v) for i, v in enumerate(arr)]
# Sort values in descending order
items = sorted(items, key=lambda item: item[1], reverse=True)
# Sack keeps track of:
# max value so i.e. sack[0] and
# count of how many each item are in the sack i.e. sack[1]
sack = [(0, [0 for i in items]) for i in range(0, C+1)] # value, [item counts]
for i,item in enumerate(items):
# For current item we check if a previous entry could have done better
# by adding this item to the sack
index, value = item
for c in range(value, C+1): # check all previous values
sackwithout = sack[c-value] # previous max sack to try adding this item to
trial = sackwithout[0] + value # adding value to max without using it
used = sackwithout[1][i] # count of i-them item
if sack[c][0] < trial:
# old max sack with this added item is better
sack[c] = (trial, sackwithout[1][:])
sack[c][1][i] +=1 # use one more
value, bagged = sack[C]
# index and count of each array value
new_bagged = [(i, v) for (i, _), v in zip(items, bagged)]
# Re-sort based upon original order of array indexes
new_bagged.sort(key=lambda t: t[0])
# counts based upon original array order
cnts = [v for i, v in new_bagged]
return sum(cnts), value, cnts
测试代码
for t in [([1, 3, 5], 8), ([3, 5, 7], 9), ([1, 3, 5], 13)]:
result = knapsack_unbounded_dp(t[0], t[1])
print(f'Test: {t[0]}, Given Sum {t[1]}')
print(f'Result counts {result[2]}, with max sum {result[1]}, Total Count {result[0]}\n')
输出
Test: [1, 3, 5], Given Sum 8
Result counts [0, 3, 0], with max sum 9, Total Count 3
Test: [3, 5, 7], Given Sum 9
Result counts [0, 2, 0], with max sum 10, Total Count 2
Test: [1, 3, 5], Given Sum 13
Result counts [0, 3, 1], with max sum 14, Total Count 4
推荐阅读
- kubernetes - Kubernetes CronJob 执行 3 次而不是 1 次
- javascript - 从父功能组件调用类子组件方法
- c# - 如何映射 IGrouping
到 IGrouping 使用Linq? - android - Android 11 - 应用之间的可共享文件
- node.js - Mongoose 在数组对象中存储相同的日期和时间
- python - 有没有办法在装饰器中包装函数调用
- node.js - Mongoose 验证器未更新
- puppeteer - 应用 backgroundColor 时 Puppeteer 隐藏单元格边框
- sql - oracle中通过添加索引进行性能调优
- python - 理解梯度计算的pytorch示例代码