python - 如何最大化加/减组合?
问题描述
假设我有一个包含 10 个元素的列表 [a、b、c、d、e、f、g、h、i、j],我可以将每个元素乘以 0、1、2、-1、-2。
我使用的乘法因子的总和必须为零。即,如果我将五个数字乘以 -1,我必须将其他五个数字乘以 1,或者我可以将 a 乘以 2,将 b 和 c 乘以 -1,其余的乘以 0。
我想找到此操作产生的总和最大的列表。
我该如何在 python 中进行编码?
我已经尝试对 [2, 1, 0, -1, -2] 的每次迭代进行编码,并删除不加到 0 的列表,然后乘以原始列表,但是我卡住了。
解决方案
您可以对列表进行排序,从末端向中心扫描,分配2
给较大的元素和-2
较小的元素。
def baby_knapsack(xs):
xs = sorted(xs, reverse=True)
res = list()
n = len(xs)
for i in range(n//2):
res.extend(((xs[i], 2), (xs[-1-i], -2)))
if n % 2 == 1:
res.append((xs[n//2], 0))
return res
xs = [-10, -5, 0, 5, 10, 15]
# In [73]: q.baby_knapsack(q.xs)
# Out[73]: [(15, 2), (-10, -2), (10, 2), (-5, -2), (5, 2), (0, -2)]
推荐阅读
- sql - 在 T-SQL 中使用 Window 函数计算类别列
- node.js - 未捕获的 ReferenceError: __webpack_dev_server_client__ 未定义
- c++ - 不同类的构造函数重载解析
- hyperlink - 如何在招摇文档中链接和引用自我?
- stripe-payments - 如何在条带元素中填充已保存的卡值?
- ruby - Cromedriver `driver.manage.logs.get(:browser)` 在 chromedriver 75.0.3770.8 上失败
- python-3.6 - 运行 python xlwings 库并失败 COMRetryObjectWrapper(DispatchEx('Excel.Application'))
- react-native - 在显示未处理的承诺拒绝时反应未定义的本机导航
- c# - 如何获取传递给我的函数的参数名称?
- powershell - Powershell 上的功能比较