Replace
if(x>=y)
{
m[i][j]=x;
//cost=wt[i];
ans[i][j]=wt[i]+ans[i-1][j-wt[i]];
}
with
if(x>y){
m[i][j] = x;
ans[i][j] = wt[i]+ans[i-1][j-wt[i]];
}else if(x==y){
m[i][j] = x;
ans[i][j] = min(ans[i-1][j] , ans[i-1][j-wt[i]]+wt[i]);
}
try it !!!!
On Wed, Oct 13, 2010 at 9:35 AM, keyankarthi <[email protected]>wrote:
> hey guys.., i tried solving this problem
> http://www.spoj.pl/problems/PARTY/
> i get answer for the test cases that i try.. getting WA in the judge..
> can anyone help me out here.. my code is as follows..
>
> #include<iostream>
> #include<stdio.h>
> using namespace std;
>
> int m[150][150],v[150],wt[150],ans[150][150];
> void dp(int weight,int n)
> {
> int i,j,x,y,anscount=0;
> for(i=0;i<=weight;i++)
> m[0][i]=0;
> for(i=1;i<=n;i++)
> ans[0][i]=0;
>
> for(i=1;i<=n;i++)
> {
> for(j=0;j<=weight;j++)
> {
> if(wt[i]<=j)
> {
> x=(v[i]+m[i-1][j-wt[i]]);
> y=(m[i-1][j]);
> if(x>=y)
> {
> m[i][j]=x;
> //cost=wt[i];
> ans[i][j]=wt[i]+ans[i-1][j-wt[i]];
> }
> else
> {
> m[i][j]=y;
> ans[i][j]=ans[i-1][j];
> }
> }
> else
> {
> m[i][j]=m[i-1][j];
> ans[i][j]=ans[i-1][j];
> }
> }
> }
> printf("%d %d",ans[n][weight],m[n][weight]);
> }
>
> int main()
> {
>
> int weight,no,i,j;
> while(1)
> {
> scanf("%d %d",&weight,&no);
> if(!weight && !no)
> break;
> for(i=1;i<=no;i++)
> scanf("%d %d",&wt[i],&v[i]);
> dp(weight,no);
> }
> }
>
> thanks,
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
Devendra Pratap Singh
B.Tech (IT)
IIIT - Allahabad
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
