Databases
StackOverflow2013
Postsdbo
POCoin change with different upper bounds on different coins?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POCoin change with different upper bounds on different coins?
    primarykey
    data
    text
    <p>Sample Input: 20 10 2 5 2</p> <p>Sample Output: 2</p> <p>Explanation: An amount of 20 could be made in 2 ways: 10*2 10*1 + 5*2</p> <p>I want to find out the number of ways a particular amount can be made with given coins.In the sample input 20 is the amount to be made and the next line shows the coin value and number of coins of that value ie 2 coins of value 10.Output has the number of ways 20 can be made with these coins.I have tried out a recursive solution but is not working properly.What algorithm should I use to solve this problem?</p> <pre><code> #include&lt;stdlib.h&gt; #include&lt;limits.h&gt; #include&lt;stdio.h&gt; typedef int (*compfn)(const void*, const void*); struct pair { int coin; int numberofcoin; }; int compare(const struct pair *elem1 ,const struct pair *elem2) { if ( elem2-&gt;coin &gt; elem1-&gt;coin &amp;&amp; elem2-&gt;numberofcoin&gt;0) return 1; else return -1; } void print(struct pair a[],int ncoin) { int i=0; putchar('\n'); for(i=0;i&lt;ncoin;i++) { printf("%d\t%d\n",a[i].coin,a[i].numberofcoin); } putchar('\n'); } int wa(int n,struct pair a[],int numberofdenominations,int current) {print(a,numberofdenominations); printf("the amount here %d\n",n); int ans=0; if(n==0) { puts("case 1\n"); return 1;} int i=0; int small=INT_MAX; for(i=0;i&lt;numberofdenominations;i++) { if(small&gt;a[i].coin&amp;&amp;a[i].numberofcoin) { small=a[i].coin; } } if(n&lt;small||n&lt;0) { puts("case 2\n"); return 0; } else { puts("case 3\n"); print(a,numberofdenominations); qsort(a, numberofdenominations, sizeof(a), (compfn)compare); puts("after sort\n"); print(a,numberofdenominations); int j=0; for(j=0;j&lt;numberofdenominations;j++) { if(a[j].numberofcoin&gt;0&amp;&amp;a[j].coin&lt;=current) { puts("case if\n"); a[j].numberofcoin--; ans+=wa(n-a[j].coin,a,numberofdenominations,a[j].numberofcoin); a[j].numberofcoin++; } } } return ans; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int nc=0; scanf("%d",&amp;nc); int amount=0; int coin[50]; int numberofcoin[50]; struct pair a[51]; int i=0; for(i=0;i&lt;nc;i++) { //scanf("%d%d",&amp;c[i],&amp;numberofcoin[i]); scanf("%d%d",&amp;a[i].coin,&amp;a[i].numberofcoin); } scanf("%d",&amp;amount); for(i=0;i&lt;nc;i++) { a[i].numberofcoin=amount/a[i].coin; } //printf("%d\n",ways(amount,coin,numberofcoin,nc,10,amount,0)); printf("%d\n",wa(amount,a,nc,10)); return 0; } </code></pre> <p>I am always getting 0 as the answer for some reason.Please all help will be appreciated.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USAjax Aristodemos
    1. USAjax Aristodemos
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POCoin change with different upper bounds on different coins?
      1. USAjax Aristodemos
      1. VTFavorite
    2. VO
      singulars
      1. POCoin change with different upper bounds on different coins?
      1. This table or related slice is empty.
      1. VTDownMod
    1. CO10 2 5 4 the amount here 20 case 3 10 2 5 4 after sort 10 2 5 4 case if 10 1 5 4 the amount here 10 case 3 10 1 5 4 after sort 10 1 5 4 case if 10 2 5 3 the amount here 15 case 3 10 2 5 3 after sort 10 2 5 3 0 The output I am getting.
      singulars
      1. POCoin change with different upper bounds on different coins?
      1. USAjax Aristodemos
    2. COThe mathematics behind your generalized question uses generating functions: http://math.stackexchange.com/questions/15521/making-change-for-a-dollar-and-other-number-partitioning-problems.
      singulars
      1. POCoin change with different upper bounds on different coins?
      1. USHooked
 

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