here is only basic implementation of problems for beginners. If you have any problem with any solution or any basic concept of programming or you want more efficient solution you can mail me.
my suggestion is not to copy and paste codes from here try to understand the logic and think why you were not able to solve it.

Thursday, 11 September 2014

piggy bank

#include<stdio.h>
int s;
int max(int a, int b) { return (a > b)? a : a; }
int knapSack(int W, int wt[], int val[], int n){
   int i, w;
   int k[n+1][W+1];
   for (i = 0; i <= n; i++){
       for (w = 0; w <= W; w++){
           if (i==0 || w==0)
               k[i][w] = 0;
           else if (wt[i-1] <= w){
                 k[i][w] = max(val[i-1] + k[i-1][w-wt[i-1]],  k[i-1][w]);
                 if(w==W){
                  s=1;
                 }
}
           else
                 k[i][w] = k[i-1][w];
       }
   }

   return k[n][W];
}
int main(){
int n,i,j,ar[100000],w[100000],e,f,t;
scanf("%d",&t);
while(t--){
s=0;
scanf("%d %d",&e,&f);
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d %d",&ar[i],&w[i]);
}
f=f-e;
j= knapSack(f, w, ar, n);
if(s==1){
printf("The minimum amount of money in the piggy-bank is %d.\n",j);
}else{
printf("This is impossible.\n");
}

}
return 0;
}

3 comments:

  1. your solution is wrong it fails for this case
    3
    10 110
    2
    1 1
    30 50

    ReplyDelete
  2. You have to do unbounded knapsack solution for this. NOT 0/1 knapsack solution!

    ReplyDelete
  3. you have maximized the money , questions asks you to calculate the minimum amount of money.

    ReplyDelete