SPOJ Problem:- PARTY - Party Schedule Solution

Read the comment for explanation. You can remove the unnecessary comments. Copy the code to your IDE for better reading then read the explanations from comment lines in code. Also please send your feed-backs. 
You can see youtube video of "Tushar Roy" on knapsack problem. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

//NAME:- ANUHAR TRIPATHI //COLLEGE:- JAYPEE UNIVERSITY OF ENGINEERING & TECHNOLOGY, GUNA //EMAIL:- anuhartripathi15@gmail.com //SPOJ Problem:- PARTY - Party Schedule #include<bits/stdc++.h> #define ll long long using namespace std; int main() { ll b,n,i,fee,fun; cin>>b>>n; while(b!=0||n!=0) { ll a[n+2][b+3]; for(i=0;i<b+1;i++) {a[0][i+2]=i;a[1][i+2]=0;} for(i=0;i<n;i++) {cin>>fee>>fun; a[i+2][0]=fee; a[i+2][1]=fun; a[i+2][2]=0;}//(double)fun/fee;} ll j,k,x,y,z; /*for(i=0;i<=n+1;i++) { for(j=0;j<b+3;j++) {cout<<a[i][j]<<" ";} cout<<"\n"; }*/ for(i=2;i<=n+1;i++) { for(j=3;j<b+3;j++) { if(a[0][j]-a[i][0]>=0) a[i][j]=max(a[i-1][j-a[i][0]]+a[i][1],a[i-1][j]); else a[i][j]=a[i-1][j]; } } //In this part we are going to find the fees amount & //maximum fun will be the last element of 2-d array 'a' x=0; i=n+1; j=b+2; while(i!=1)//&&j!=2) { while(a[i][j]==a[i][j-1]&&j!=3) j--; if(a[i][j]==a[i-1][j]); /*{ if(a[0][j]-a[i][0]>=0&&a[i-1][j-a[i][0]]==a[i][j]) {x+=a[i][0];if(a[0][j]-a[i][0]>=0)j-=a[i][0];} }*/ else {x+=a[i][0];if(a[0][j]-a[i][0]>=0)j-=a[i][0];} --i; } cout<<x<<" "<<a[n+1][b+2]<<"\n"; cin>>b>>n; } return 0; }