一家商店正在大减价。如果你方价格达到199美元或更多,你可以降低100美元。You只能购买每种产品一次。下面是一个产品示例列表:(为了简化,产品名称用字母表示)
+------+-------+
| name | price |
+------+-------+
| A | 26.9 |
| B | 24.9 |
| C | 49.9 |
| D | 28.9 |
| E | 14.9 |
| F | 16.9 |
| G | 19.9 |
| H | 19 |
| I | 14.9 |
| J | 14.9 |
| K | 26.9 |
+------+-------+N项目列表大小10 <= N <= 100X a价格省钱的最佳购物策略。找出总价格高于X的最便宜的购买清单,并输出:
X =199美元,最合适的总价是199.2。发布于 2019-03-05 09:41:14
O(2^{n/2})import sys
def subsetsum(nums, target):
# totalsum = sum(nums)
# if(totalsum == target):
# return target
# if(totalsum < target):
# return -1
sumsA = {}
sumsB = {}
for n in nums[::2]:
for k,v in sumsA.items() + [(0,[])]:
newsum = k + n
if newsum not in sumsA:
sumsA[newsum] = v + [n]
if newsum == target:
print "target found in sumsA loop: "
return target
minsum = sys.maxsize
for n in nums[1::2]:
for k,v in sumsB.items() + [(0,[])]:
newsum = k + n
if newsum not in sumsB:
sumsB[newsum] = v + [n]
if newsum == target:
print "target found in sumsB loop: "
return target
for a in sumsA:
combsum = a + newsum
if combsum == target:
print "target found in combined sumsA and sumsB loop: "
return target
if combsum > target and combsum < minsum:
minsum = combsum
print "target",target,"not found, so return the closest alternative: "
return minsum
# Test cases:
print subsetsum([26.9, 24.9, 49.9, 28.9, 14.9, 16.9, 19.9, 19, 14.9, 14.9, 26.9], 199)
print subsetsum([47.5, 1.0, 19.6, 16.7, 21.8, 5.6, 40.4, 31.8, 25.4, 21.9,
21.7, 17.6, 48.4, 17.4, 41.1, 8.9, 12.2, 25.6, 28.5, 26.3,
21.3, 35.1, 37.8, 45.1, 28.5, 47.6, 33.9, 21.5, 34.3, 14.2,
40.9, 17.9, 44.9, 44.2, 20.5, 30.8, 43.0, 24.5, 20.1, 46.7,
49.6, 42.1, 19.8, 3.8, 0.2, 38.3, 21.3, 15.3, 11.2, 36.0], 1000)
print subsetsum([47.5, 1.0, 19.6, 16.7, 21.8, 5.6, 40.4, 31.8, 25.4, 21.9,
21.7, 17.6, 48.4, 17.4, 41.1, 8.9, 12.2, 25.6, 28.5, 26.3,
21.3, 35.1, 37.8, 45.1, 28.5, 47.6, 33.9, 21.5, 34.3, 14.2,
40.9, 17.9, 44.9, 44.2, 20.5, 30.8, 43.0, 24.5, 20.1, 46.7,
49.6, 42.1, 19.8, 3.8, 0.2, 38.3, 21.3, 15.3, 11.2, 36.0], 555.5)我的Python技巧有点生疏,所以如果你看到任何问题,请告诉我。此外,我认为可以通过一些二进制搜索或类似的方法,在代码中对此进行改进。
该程序使用背包会合中法。它首先使用所有偶数索引项为这些偶数索引项的powerset获取一组可能的总和。然后,它对所有奇数索引项做相同的操作,同时使用这两个集合的和来确定最小和。
https://codegolf.stackexchange.com/questions/180841
复制相似问题