WA in Party

[havingfun_sof]

Accepted at last...

[zrbrxc]

(invalid test case removed)

[havingfun_sof]

Allowed range for Party cost is from 5 to 25...
So it can't be 3 as in your i/p...
I have checked conditions for cost>=5 && cost<=25...

[zrbrxc]

How about this one?
Input:

103 5
13 0
21 10
18 9
19 7
15 2
0 0

Output:

73 28

Your output:

86 28

[havingfun_sof]

Can you tell.. Where I am wrong....

I have changed one thing
Now I am checking not to take those parties for which fun = 0

if(gen[V[i-1]][xx] && V[i-1]!=0)
          {val+=xx;gen[V[i-1]][xx]-=1;break;}

Still wrong answer...
which part is wrong please help...

[zrbrxc]

I don't know what's wrong with your code. You can start by enabling warnings in your compiler:

f.cpp: In function 'int main()':
f.cpp:17: warning: missing braces around initializer for 'int [26]'
f.cpp:21: warning: missing braces around initializer for 'bool [501]'

Input:

37 59
20 5
7 2
13 8
8 0
9 9
19 4
9 5
16 6
17 1
19 0
12 10
13 0
7 9
6 7
15 0
20 10
18 6
11 10
8 2
22 3
16 7
15 6
17 4
20 1
10 3
24 9
23 6
23 6
11 4
17 0
5 1
24 3
24 8
12 2
22 2
12 7
12 1
10 8
13 4
9 2
10 5
20 9
23 0
22 3
17 1
12 8
15 7
12 4
17 4
22 7
19 8
5 2
25 6
22 9
11 6
20 2
8 9
7 0
8 1
0 0

Output:

35 37

Your output:

37 37

Edit: and a shorter one:
Input:

78 20
24 6
24 8
13 0
23 5
5 10
12 3
14 1
12 5
10 9
21 10
20 5
20 2
11 10
13 8
11 1
10 7
13 7
8 2
24 9
20 0
0 0

Output:

74 56

Your output:

78 56

[havingfun_sof]

[quote="zrbrxc"]I don't know what's wrong with your code. You can start by enabling warnings in your compiler:

f.cpp: In function 'int main()':
f.cpp:17: warning: missing braces around initializer for 'int [26]'
f.cpp:21: warning: missing braces around initializer for 'bool [501]'

Input:

37 59
20 5
7 2
13 8
8 0
9 9
19 4
9 5
16 6
17 1
19 0
12 10
13 0
7 9
6 7
15 0
20 10
18 6
11 10
8 2
22 3
16 7
15 6
17 4
20 1
10 3
24 9
23 6
23 6
11 4
17 0
5 1
24 3
24 8
12 2
22 2
12 7
12 1
10 8
13 4
9 2
10 5
20 9
23 0
22 3
17 1
12 8
15 7
12 4
17 4
22 7
19 8
5 2
25 6
22 9
11 6
20 2
8 9
7 0
8 1
0 0

Output:

35 37

Your output:

37 37

Edit: and a shorter one:
Input:

78 20
24 6
24 8
13 0
23 5
5 10
12 3
14 1
12 5
10 9
21 10
20 5
20 2
11 10
13 8
11 1
10 7
13 7
8 2
24 9
20 0
0 0

Output:

74 56

Your output:

78 56

[/quote]

Thanxxx zrbrxc...

[Ankush101_sof]

I'm not able to get why i'm getting WA.Any help would be appreciated

#include <stdio.h>
int main(void) {
	// your code goes here
	int budget,parties,i,j,best;
	while(scanf("%d %d",&budget,&parties)>=2){
		if(!budget && !parties) break;
		int  fun[parties];
		int  cost[parties];
		int  funvalue[budget+1][parties+1];
		int  totamount[budget+1][parties+1];
		for(i=0;i<parties;i++){
			fun[i]=cost[i]=0;
		}
		for(i=0;i<parties;i++)
			scanf("%d %d",&cost[i],&fun[i]);
		for(i=0;i<=parties;i++){
			funvalue[0][i]=0;
			totamount[0][i]=0;
		}
		for(i=1;i<=budget;i++){
			funvalue[i][0]=0;
			totamount[i][0]=0;
		}
		for(i=1;i<=budget;i++){
			for(j=1;j<=parties;j++){
				if(i>cost[j-1]){
					if(funvalue[i-cost[j-1]][j-1] + fun[j-1] > funvalue[i][j-1]){
						funvalue[i][j]=funvalue[i-cost[j-1]][j-1] + fun[j-1];
						totamount[i][j]=totamount[i-cost[j-1]][j-1]+ cost[j-1];
					}
					else{
						funvalue[i][j]=funvalue[i][j-1];
						totamount[i][j]=totamount[i][j-1];
					}
				}
				else{
						funvalue[i][j]=funvalue[i][j-1];
						totamount[i][j]=totamount[i][j-1];
				}
			}
		}
		/*for(i=0;i<=budget;i++){
			for(j=0;j<=parties;j++){
				printf("%d ",funvalue[i][j]);
			}
			printf("\n");
		}
		printf("\n");
		printf("\n");
		for(i=0;i<=budget;i++){
			for(j=0;j<=parties;j++){
				printf("%d ",totamount[i][j]);
			}
			printf("\n");
		}
		*/
		 for(i = budget, best = funvalue[budget][parties]; i; i--){
                        if(funvalue[i][parties] == best){
                        	continue;
                        }     
                        else{
                               	break;
                               } 
		 }
		printf("%d %d\n",totamount[i+1][parties],funvalue[budget][parties]);
	}
	return 0;
}

[wagon]

I'm getting wa in PARTY it is giving correct o/p for sample testcases. Plz help.

#include<iostream>
using namespace std;
int funlevel(int a[][2],int b,int n,int& cost,int k,int dp[][600][2])
{
	if(b>0&&dp[k][b][0]!=-1)
	{
		cost=dp[k][b][1];
		return dp[k][b][0];
	}
	else{
	if(b<=0)
	{
		cost=0;
		return 0;
	}
	if(k==n-1)
	{
		if(b>=a[k][0])
		{
			cost=a[k][0];
			dp[k][b][1]=cost;
			dp[k][b][0]=a[k][1];
			return a[k][1];
		}
		else
		{
			cost=0;
			dp[k][b][1]=0;
			dp[k][b][0]=0;
			return 0;
		}
	}
	else{
	int cost1,cost2;
	int fun1=funlevel(a,b,n,cost1,k+1,dp);
	int d=b-a[k][0];
	int fun2=0;
	if(d>0)  fun2=a[k][1]+funlevel(a,d,n,cost2,k+1,dp);
	if(fun1>fun2)
	{
		cost=cost1;
		dp[k][b][1]=cost;
		dp[k][b][0]=fun1;
		return fun1;
	}
	else if(fun2>fun1)
	{
		cost=a[k][0]+cost2;
		dp[k][b][1]=cost;
		dp[k][b][0]=fun2;
		return fun2;
	}
	else
	{
		if(cost1<a[k][0]+cost2)
		{
			cost=cost1;
			dp[k][b][1]=cost;
			dp[k][b][0]=fun1;
			return fun1;
		}
		else
		{
			cost=a[k][0]+cost2;
			dp[k][b][1]=cost;
			dp[k][b][0]=fun2;
			return fun2;
		}
	}
	}
	}
}
int main()
{
    while(1)
{
	int b,n,a[100][2],cost,dp[200][600][2];
	cin>>b>>n;
	if(b==0&&n==0) break;
	for(int i=0;i<n;i++) cin>>a[i][0]>>a[i][1];
	for(int i=0;i<100;i++)
	{
		for(int j=0;j<500;j++)
		{
			dp[i][j][0]=-1;
			dp[i][j][1]=-1;
		}
	}
	int d=funlevel(a,b,n,cost,0,dp);
	cout<<cost<<" "<<d<<endl;
}
}

[arv]

GEtting WA even though my code passes all the test cases in the forum !!
I think , there may be a problem in output format or the input format !
Please help !

#include<stdio.h>
#include<string.h>
static int weight=0;
int Knapsack(int W,int v[],int wt[],int n)
{
    int i=0,w=0,et=0,tr=0,min=0,j=0,KT=0,call=0;
    int keeper[n+1][W+1];
    int k[n+1][W+1];
    int keep[n+1];
    int flag=0;
    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)
          {
              if((v[i-1]+k[i-1][w-wt[i-1]])>k[i-1][w])
              {
            k[i][w]=v[i-1]+k[i-1][w-wt[i-1]];
            keeper[i][w]=1;
              }
              else
           {
              k[i][w]=k[i-1][w];
              keeper[i][w]=0;
           }
          }
          else
            {
              k[i][w]=k[i-1][w];
              keeper[i][w]=0;
           }
        }
}
    }
     KT=W;
     for(i=n;i>=1;i--)
     {
         if(keeper[i][KT]==1)
         {
            keep[et]=v[i-1];
            et+=1;
            KT-=wt[i-1];
            }
     }
    for(i=0;i<et;i++)
    {
          min=26;
        for(j=0;j<n;j++)
        {
            if(v[j]==keep[i])
            {
                if(min>wt[j])
                   {
                     min = wt[j];
                     call=j;
                   }
            }
        }
        if(min!=26)
        {
        weight+=min;
        v[call]=11;
        }
    }
    return k[n][W];
}
int main()
{
int n=0,W=0,i=0,p=0,max=0,j=0;
while(1)
{
scanf("%d%d\n",&W,&n);
if(W==0 && n==0)
    break;
int wt[n];
int fun[n];
for(i=0;i<n;i++)
scanf("%d%d\n",&wt[i],&fun[i]);
p=Knapsack(W,fun,wt,n);
printf("%d %d\n",weight,p);
weight=0;
}
return 0;
}