Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>We need to know two pieces of information:</p> <ul> <li>when a coin is chosen for the optimal solution</li> <li>which coin was chosen for the optimal solution</li> </ul> <p>According to your algorithm, we know that we select a coin whenever you return <code>1</code>. We also know that the coin chosen at that the index of the coin chosen is <code>start</code>. Thus, we have information to solve this problem.</p> <p>Since performance isn't a problem here, we will simply pass a coins parameter that is filled as the coins are selected.</p> <pre><code>public static int dynamicCoinChange(int[] denoms, int amt, int start, ArrayList&lt;Integer&gt; coins) { if (amt == 0 || start &lt; 0) { return 0; } else if (amt == 1) { coins.add(1); return 1; } else if (denoms[start] &gt; amt // Note that these calls are not guaranteed to be in our solution // Thus, we make a copy to prevent the calls from modifying our solution || dynamicCoinChange(denoms, amt, start-1, new ArrayList&lt;Integer&gt;(coins)) &lt; (1 + dynamicCoinChange(denoms, amt-denoms[start], start, new ArrayList&lt;Integer&gt;(coins))) &amp;&amp; !(dynamicCoinChange(denoms, amt, start-1, new ArrayList&lt;Integer&gt;(coins)) == 0)) { return dynamicCoinChange(denoms, amt, start-1, coins); } else { coins.add(denoms[start]); return 1 + dynamicCoinChange(denoms,amt-denoms[start], start, coins); } } </code></pre> <p>Since this requires us to change our method signature, we must also modify our driver:</p> <pre><code>public static void main(String[] args) { int[] denoms = {1, 6, 10, 25}; ArrayList&lt;Integer&gt; coins = new ArrayList&lt;Integer&gt;(); int numCoins = dynamicCoinChange(denoms, 7, 3, coins); for (Integer coin : coins) System.out.println(coin); System.out.println(numCoins); } </code></pre> <p>At the end of the recursive calls, <code>coins</code> should contain the list of coins chosen in chronological order.</p>
    singulars
    1. This table or related slice is empty.
    1. POTrouble printing out denominations used in Minimum Change algorithm
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USGio Borje
    1. USGio Borje
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POTrouble printing out denominations used in Minimum Change algorithm
      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. VTAcceptedByOriginator
    1. CONo, this won't work because we're essentially calculating lots of *possible* solutions and then choosing one based on comparison. Yeah, I know it's inefficient haha.
      singulars
      1. PO
      1. USMassStrike
    2. COIf you remove the latter half of your second-to-last condition, `|| dynamicCoinChange(denoms, amt, start-1) < (1 + dynamicCoinChange(denoms, amt-denoms[start], start)) && !(dynamicCoinChange(denoms, amt, start-1) == 0)` this should still work fine.
      singulars
      1. PO
      1. USGio Borje
    3. COYou mean remove beginning with '||' or beginning with '&&'?
      singulars
      1. PO
      1. USMassStrike
 

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