I am trying to solve a spoj problem Party Schedule
the problem statement is-
You just received another bill which you cannot pay because you lack the money.
Unfortunately, this is not the first time to happen, and now you decide to investigate the cause
of your constant monetary shortness. The reason is quite obvious: the lion's share
of your money routinely disappears at the entrance
of party localities.
You make up your mind to solve the problem where it arises, namely at the parties themselves. You introduce a limit for your party budget and try to have the most possible fun with regard to this limit.
You inquire beforehand about the entrance fee to each party and estimate how much fun you might have there. The list is readily compiled, but how do you actually pick the parties that give you the most fun and do not exceed your budget?
Write a program which finds this optimal set
of parties that offer the most fun. Keep in mind that your budget need not necessarily be reached exactly. Achieve the highest possible fun level, and do not spend more money than is absolutely necessary.
Input
The first line
of the input specifies your party budget and the number n
of parties.
The following n lines contain two numbers each. The first number indicates the entrance fee
of each party. Parties cost between 5 and 25 francs. The second number indicates the amount
of fun
of each party, given as an integer number ranging from 0 to 10.
The budget will not exceed 500 and there will be at most 100 parties. All numbers are separated by a single space.
There are many test cases. Input ends with 0 0.
Output
For each test case your program must output the sum
of the entrance fees and the sum
of all fun values
of an optimal solution. Both numbers must be separated by a single space.
Example
Sample input:
50 10
12 3
15 8
16 9
16 6
10 2
21 9
18 4
12 4
17 8
18 9
50 10
13 8
19 10
16 8
12 9
10 2
12 8
13 5
15 5
11 7
16 2
0 0
Sample output:
49 26
48 32
now I know that it is an advance version
of 0/1 knapsack problem where along with
maximum cost we also have to find minimum weight that is less than a a given weight and have
maximum cost.
so I have used dp to solve this problem but still get a wrong awnser on submission while it is perfectly fine with given test cases.
My code is
typedef vector<int> vi;
#define pb push_back
#define FOR(i,n) for(int i=0;i<n;i++)
int main()
{
//freopen("input.txt","r",stdin);
while(1)
{
int W,n;
cin>>W>>n;
if(W==0 && n==0)
break;
int K[n+1][W+1];
vi val,wt;
FOR(i,n)
{
int x,y;
cin>>x>>y;
wt.pb(x);
val.pb(y);
}
FOR(i,n+1)
{
FOR(w,W+1)
{
if(i==0 || w==0)
{
K[i][w]=0;
}
else if (wt[i-1] <= w)
{
if(val[i-1] + K[i-1][w-wt[i-1]]>=K[i-1][w])
{
K[i][w]=val[i-1] + K[i-1][w-wt[i-1]];
}
else
{
K[i][w]=K[i-1][w];
}
}
else
{
K[i][w] = K[i-1][w];
}
}
}
int a1=K[n][W],a2;
for(int j=0;j<W;j++)
{
if(K[n][j]==a1)
{
a2=j;
break;
}
}
cout<<a2<<" "<<a1<<"\n";
}
return 0;
}
Could anyone suggest what am I missing??
