PYTHON: Suppose three people acquire a bag of jewels, and know the exact (positi

Question

PYTHON:

Suppose three people acquire a bag of jewels, and know the exact (positive) value of each. They wish to know whether or not is is possible to divide up the jewels so that they each get exactly one third of the value. Your first task is to write python function share to solve the problem, this should take a list of the values. Your code should return True or False depending on whether there is a fair share possible, and the function should print out a fair share if it finds one.

For example:

print(share([434,722,50,334,50,178,333,303,30,566]))

Should output:

Fair share found: [434, 566] [722, 50, 50, 178] [334, 333, 303, 30]

True

False

Your goal is to make code that works. It will probably not be fast. What is the runtime of your code, using N to represent the size of the array? How big of an N can it handle before it slows down on your computer?

Explanation / Answer

def share(jewels_list):
sum_jewels = sum(jewels_list)
if sum_jewels % 3 != 0:
print "Can't be partitioned in 3"
return False
required_sum = sum_jewels/3
subsetSum = [0,0,0]
taken = [-1]*len(jewels_list)
subsetSum[0] = jewels_list[-1]
taken[-1] = 0
if required_sum < subsetSum[0]:
return False
isequal = shareHelperRec(jewels_list, subsetSum, taken, required_sum, 3, len(jewels_list), 0, len(jewels_list) -1)
return isequal

def shareHelperRec(arr, subsetSum, taken, subset, K, N, curIdx, limitIdx):
if subsetSum[curIdx] == subset:
# current index (K - 2) represents (K - 1) subsets of equal
# sum last subsetition will already remain with sum 'subset'
if (curIdx == K - 2):
return True;

# recursive call for next subsetition
return shareHelperRec(arr, subsetSum, taken, subset, K, N, curIdx + 1, N - 1)

# start from limitIdx and include elements into current subsetition
for i in range(limitIdx, -1, -1):
# if already taken, continue
if (taken[i] != -1):
continue;
tmp = subsetSum[curIdx] + arr[i]

# if temp is less than subset then only include the element
# and call recursively
if (tmp <= subset):
# mark the element and include into current subsetition sum
taken[i] = curIdx;
subsetSum[curIdx] += arr[i];
nxt = shareHelperRec(arr, subsetSum, taken, subset, K, N, curIdx, i - 1);

# after recursive call unmark the element and remove from
# subsetition sum
taken[i] = -1;
subsetSum[curIdx] -= arr[i];
if (nxt):
return True;
return False;

print(share([434,722,50]))

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.