Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>This is a great algorithms question, but to be honest I don't think your implementation is correct or it could be that I don't understand the input/output of your function, for that I apologize.<br></p> <p>heres a modified version of your implementation.<br></p> <pre><code>def C(i, coins, cdict = None): if cdict == None: cdict = {} if i &lt;= 0: cdict[i] = 0 return cdict[i] elif i in cdict: return cdict[i] elif i in coins: cdict[i] = 1 return cdict[i] else: min = 0 for cj in coins: result = C(i - cj, coins) if result != 0: if min == 0 or (result + 1) &lt; min: min = 1 + result cdict[i] = min return cdict[i] </code></pre> <p>This is my attempt at solving a similar problem, but this time returning a list of coins. I initially started with a recursive algorithm, which accepts a sum and a list of coins, which may return either a list with the minimun number of coins or None if no such configuration could be found.</p> <pre><code>def get_min_coin_configuration(sum = None, coins = None): if sum in coins: # if sum in coins, nothing to do but return. return [sum] elif max(coins) &gt; sum: # if the largest coin is greater then the sum, there's nothing we can do. return None else: # check for each coin, keep track of the minimun configuration, then return it. min_length = None min_configuration = None for coin in coins: results = get_min_coin_configuration(sum = sum - coin, coins = coins) if results != None: if min_length == None or (1 + len(results)) &lt; len(min_configuration): min_configuration = [coin] + results min_length = len(min_configuration) return min_configuration </code></pre> <p>ok now lets see if we can improve it, by using dynamic programming (I just call it caching).</p> <pre><code>def get_min_coin_configuration(sum = None, coins = None, cache = None): if cache == None: # this is quite crucial if its in the definition its presistent ... cache = {} if sum in cache: return cache[sum] elif sum in coins: # if sum in coins, nothing to do but return. cache[sum] = [sum] return cache[sum] elif max(coins) &gt; sum: # if the largest coin is greater then the sum, there's nothing we can do. cache[sum] = None return cache[sum] else: # check for each coin, keep track of the minimun configuration, then return it. min_length = None min_configuration = None for coin in coins: results = get_min_coin_configuration(sum = sum - coin, coins = coins, cache = cache) if results != None: if min_length == None or (1 + len(results)) &lt; len(min_configuration): min_configuration = [coin] + results min_length = len(min_configuration) cache[sum] = min_configuration return cache[sum] </code></pre> <p>now lets run some tests.</p> <pre><code>assert all([ get_min_coin_configuration(**test[0]) == test[1] for test in [({'sum':25, 'coins':[1, 5, 10]}, [5, 10, 10]), ({'sum':153, 'coins':[1, 5, 10, 50]}, [1, 1, 1, 50, 50, 50]), ({'sum':100, 'coins':[1, 5, 10, 25]}, [25, 25, 25, 25]), ({'sum':123, 'coins':[5, 10, 25]}, None), ({'sum':100, 'coins':[1,5,25,100]}, [100])] ]) </code></pre> <p>granted this tests aren't robust enough, you can also do this.</p> <pre><code>import random random_sum = random.randint(10**3, 10**4) result = get_min_coin_configuration(sum = random_sum, coins = random.sample(range(10**3), 200)) assert sum(result) == random_sum </code></pre> <p>its possible that the no such combination of coins equals our random_sum but I believe its rather unlikely ...</p> <p>Im sure there are better implementation out there, I tried to emphasize readability more than performance. good luck. </p> <p><b>Updated</b> the previous code had a minor bug its suppose to check for min coin not the max, re-wrote the algorithm with pep8 compliance and returns <code>[]</code> when no combination could be found instead of <code>None</code>.</p> <pre><code>def get_min_coin_configuration(total_sum, coins, cache=None): # shadowing python built-ins is frowned upon. # assert(all(c &gt; 0 for c in coins)) Assuming all coins are &gt; 0 if cache is None: # initialize cache. cache = {} if total_sum in cache: # check cache, for previously discovered solution. return cache[total_sum] elif total_sum in coins: # check if total_sum is one of the coins. cache[total_sum] = [total_sum] return [total_sum] elif min(coins) &gt; total_sum: # check feasibility, if min(coins) &gt; total_sum cache[total_sum] = [] # no combination of coins will yield solution as per our assumption (all +). return [] else: min_configuration = [] # default solution if none found. for coin in coins: # iterate over all coins, check which one will yield the smallest combination. results = get_min_coin_configuration(total_sum - coin, coins, cache=cache) # recursively search. if results and (not min_configuration or (1 + len(results)) &lt; len(min_configuration)): # check if better. min_configuration = [coin] + results cache[total_sum] = min_configuration # save this solution, for future calculations. return cache[total_sum] assert all([ get_min_coin_configuration(**test[0]) == test[1] for test in [({'total_sum':25, 'coins':[1, 5, 10]}, [5, 10, 10]), ({'total_sum':153, 'coins':[1, 5, 10, 50]}, [1, 1, 1, 50, 50, 50]), ({'total_sum':100, 'coins':[1, 5, 10, 25]}, [25, 25, 25, 25]), ({'total_sum':123, 'coins':[5, 10, 25]}, []), ({'total_sum':100, 'coins':[1,5,25,100]}, [100])] ]) </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POrecursively implementing 'minimum number of coins' in python
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USSamy Vilar
    1. USSamy Vilar
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POrecursively implementing 'minimum number of coins' in python
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. COVery clear answer. ty!
      singulars
      1. PO
      1. USuser5198
    2. COno problem, I thought it was a great algorithm assignment, and very good way to teach recursion + dynamic programming :)
      singulars
      1. PO
      1. USSamy Vilar
    3. CO@samy.vilar its output is nothing !!
      singulars
      1. PO
      1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload