考虑到这些测试用例:
votes = [6]*28
m = 10
votes1 = [5]*28+[6]*2
m1 = 10
votes2 = [5]*29+[10]*1
m2 = 10
votes3 = [8, 8, 16, 12, 12, 12, 4, 4, 12, 4, 4, 4, 8, 12, 12, 8, 8, 16, 12, 4, 16, 16, 12, 16, 12, 16, 12, 4, 16, 4, 4, 12, 4, 12, 12, 4, 16, 12, 16, 8]
m3 = 20
votes4 = [22, 21, 34, 39, 28, 33, 32, 40, 22, 34, 36, 27, 37, 34, 40, 38, 39, 32, 37, 40, 31, 37, 22, 21, 35, 34, 24, 40, 34, 21, 24, 20, 30, 31, 22, 30, 31, 25, 20, 38, 24, 23, 32, 27, 20, 31, 27, 32, 22, 32, 33, 34, 40, 38, 36, 29, 34, 24, 24, 39, 32, 37, 30, 20, 29, 26, 36, 40, 34, 22, 30, 27, 38, 27, 26, 28, 23, 40, 31, 22, 23, 35, 23, 31, 23, 39, 30, 20, 20, 35, 27, 23, 23, 29, 40, 20, 34, 40, 28, 25]
m4 = 50
votes5 = [25, 25, 25, 24, 25, 24, 24, 25, 26, 25, 26, 24, 25, 26, 24, 26, 24, 26, 26, 25, 26, 24, 26, 24, 26, 26, 26, 25, 25, 26, 24, 26, 25, 25, 24, 25, 25, 26, 26, 26, 25, 26, 25, 26, 25, 25, 24, 24, 24, 25, 24, 26, 25, 24, 26, 24, 24, 26, 24, 26, 24, 24, 24, 26, 24, 25, 24, 26, 25, 25, 26, 25, 25, 25, 25, 26, 25, 24, 25, 25, 24, 24, 24, 26, 26, 26, 25, 24, 25, 25, 25, 26, 25, 24, 26, 24, 25, 26, 24, 26]
m5 = 50
给定以下界限:
^{pr2}$我想找出是否有一个长度正好为len(votes)/2
的子集之和,它满足给定的upperbound
和{
下面是我用背包解决问题的尝试,但它没有考虑子集的长度。在
import math
def winnable(votes, m):
n = len(votes) # Number of columns
v = sum(votes)
ub = upperbound(v, m, n)
lb = lowerbound(m, n)
max_possible = knapSack(ub, votes, n)
if max_possible < lb:
return "not possible"
else:
return "possible"
def knapSack(ub, val, n):
K = [[0 for x in range(ub + 1)] for x in range(n + 1)]
# Build table K[][] in bottom up manner
for i in range(n + 1):
for w in range(ub + 1):
if i == 0 or w == 0:
K[i][w] = 0
elif val[i - 1] <= w:
K[i][w] = max(val[i - 1] + K[i - 1][w - val[i - 1]], K[i - 1][w])
else:
K[i][w] = K[i - 1][w]
return K[n][ub]
是否可以进一步修改我的解决方案以考虑子集中元素的数量。在
我已经实现了@mrmcgreg向问题添加额外维度的建议
测试:
^{pr2}$这是一个合理有效的解决方案的核心。轻微测试,但可能是正确的。(最大的问题是,您希望解决方案包括边界还是排除它们?)在
用它来解决你的问题。。。在
^{pr2}$相关问题 更多 >
编程相关推荐