Find whether there is a sum of subsets of n/2 elements satisfying the inequality?… here is a solution to the problem.
Find whether there is a sum of subsets of n/2 elements satisfying the inequality?
Given these test cases:
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
Given the following bounds:
def upperbound(v, m, n):
return math.floor(v - 0.25 * m * n - 1)
def lowerbound(m, n):
return math.ceil(0.25 * m * n + 1)
I want to find out if there is a subset of length exactly sum of len(votes)/2 to satisfy the given upperbound and lowerbound
Below is my attempt to solve the problem with a backpack, but it doesn’t take into account the length of the subset.
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]
Could it be possible to further modify my solution to account for the number of elements in the subset.
Solution
I’ve implemented the proposal of @mrmcgreg add an extra dimension to the problem
import math
def has_valid_subset(votes, m):
n = len(votes)
sum_min = math.ceil(0.25 * m * n + 1)
sum_max = math.floor(sum(votes) - 0.25 * m * n - 1)
n_half = n // 2
K = [[[(False, 0) for elements in range(min(n_half + 1, index + 1))]
for index in range(len(votes) + 1)]
for weight in range(sum_max + 1)]
for weight in range(sum_max + 1):
for index in range(len(votes) + 1):
if index == 0:
K[weight][index][0] = (True, 0)
continue
v = votes[index - 1]
for elements in range(min(n_half + 1, index)):
if v > weight:
K[weight][index][elements] = K[weight][index - 1][elements]
else:
skip_ok, skip_w = K[weight][index - 1][elements]
add_ok, add_prev_w = K[weight - v][index - 1][elements - 1]
add_w = add_prev_w + v
if skip_ok and add_ok:
K[weight][index][elements] = (True, max(skip_w, add_w))
elif skip_ok:
K[weight][index][elements] = (True, skip_w)
elif add_ok:
K[weight][index][elements] = (True, add_w)
b_max, w_max = K[-1][-1][-1]
if not b_max:
return False
return w_max >= sum_min
Test:
votes = [6]*28
m = 10
print(has_valid_subset(votes, m))
# True
votes1 = [5]*28+[6]*2
m1 = 10
print(has_valid_subset(votes1, m1))
# True
votes2 = [5]*29+[10]*1
m2 = 10
print(has_valid_subset(votes2, m2))
# False
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
print(has_valid_subset(votes3, m3))
# False
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
print(has_valid_subset(votes4, m4))
# True
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
print(has_valid_subset(votes5, m5))
# True