#=======================================================================
# Author: Isai Damier
# Title: Subset Sum with Endless Supplies
# Project: geekviewpoint
# Package: algorithms
#
# Statement:
# Given a sequence S, with n positive numbers totaling to T, check
# whether there exists a subsequence totaling to x, where x is less
# than or equal to T. You may use any of the elements in S more than
# once.
#
# Time-complexity: pseudo-polynomial: O(n*x)
# Space-complexity: O(x)
#
# Dynamic Programming Strategy:
#
# We are not going to say too much here since this is essentially the
# "Positive Subset Sum" problem. So we will wait right here as you
# go read the "Positive Subset Sum" implementation.
#
# Okay. So there is one distinction between the two problems: here you
# may use each elements as many times as you need. So given the sequence
# S={2,8,24}, we can reach 6 as 2+2+2 or 20 as 8+8+2+2.
#
# To achieve this multiplicity, all we have to change is the direction
# of the nested for-loop so that we end up with:
#
# for(int e : S)
# for(int i=0; i<=x; i++)
# if(sum[i])
# sum[i+e]=true;
#
# The reason it's that simple is because the line "if(sum[i])" is
# most of the time looking at multiples. For instance, during the first
# pass of the outer for-loop (i.e. e=2), the second for-loop sets all
# multiples of 2 to true. Manually run the example where S={2,8,24}
# and x=18 if you still don't see it.
#=======================================================================
def subsetSumEndlessReuse( S, x ):
# preliminary
if x < 0 or x > sum( S ) :
return False
# algorithm
sum_list = [False] * ( x + 1 )
sum_list[0] = True
p = 0
while not sum_list[x] and p < len( S ):
e, q = S[p], 0
while not sum_list[x] and q <= x:
if q + e <= x and sum_list[q]:
sum_list[q + e] = True
q += 1
p += 1
return sum_list[x]
import unittest
from dynamic_programming import SubsetSumWithMultipleSupplies as algorithm
class Test( unittest.TestCase ):
def testPositiveSubsetSum( self ):
S = [2, 8, 24]
for x in range( 24 + 8 + 2, -1, -2 ):
self.assertTrue( algorithm.subsetSumEndlessReuse( S, x ) )
for x in range( 24 + 8 + 2 - 1, 0, -2 ):
self.assertFalse( algorithm.subsetSumEndlessReuse( S, x ) )
