WA in PARTY

[andypertamax]

It gives correct answer for the sample input, and also some test cases I found around here

 Accepted

[leppyr64]

Presume that if at he current i you find that item j is better than the current answer. You now mark j flagged for this i. Now presume that at j+1 you find a better solution for this i than j. Now you have flagged j incorrectly.

It would be best if you had your primary loop (i) iterate from 0 to n.

[andypertamax]

Presume that if at he current i you find that item j is better than the current answer. You now mark j flagged for this i. Now presume that at j+1 you find a better solution for this i than j. Now you have flagged j incorrectly.

It would be best if you had your primary loop (i) iterate from 0 to n.

now I see the flaw in my logic

got accepted after adding else statement in flagging, thanks you very much!

[vickywiz]

WA in PARTY... Cant figure out wats wring with this code..plzz help....

#include<stdio.h>
struct a
{
int cost;
int fun;
};
int main()
{
int max,n;
while(scanf("%d%d",&max,&n) && max && n)
{
struct a obj[n+1];
int i;
for(i=1;i<=n;i++)
{
scanf("%d%d",&obj[i].cost,&obj[i].fun);
}
int m[n+1][max+1];
int w=0;
int sum=0;
for(w=0;w<=max;w++)
m[0][w]=0;
for(i=1;i<=n;i++)
{
m[i][0]=0;
for(w=1;w<=max;w++)
{
if(obj[i].cost<=w)
{
if((obj[i].fun+m[i-1][w-obj[i].cost])>m[i-1][w])
{
m[i][w]=obj[i].fun+m[i-1][w-obj[i].cost];
}
else
m[i][w]=m[i-1][w];
}
else
{
m[i][w]=m[i-1][w];
}
// printf("%d ",m[i][w]);
}
// putchar('\n');
}
i=n;
w=max;
//printf("\n\n\n");
while(i>0 && w>0)
{
if(m[i][w]!=m[i-1][w])
{
//printf("Including %d\n",obj[i].cost);
sum+=obj[i].cost;
w-=obj[i].cost;
i--;
}
else
{
i--;
}
}
printf("%d %d\n",sum,m[n][max]);
}
return 0;
}

[kcode_sof]

7 2
6 1
5 1
0 0

...and do not spend more money than is absolutely necessary.

Your output is 6, which should be 5.

PS - I haven't solved it yet.