11450 - Wedding shopping

[andmej]

I think this problem can be solved using dynamic programming. However, I haven't been able to find the recurrent relation.

Any advice?

[Samiul]

You are given the amount of money, which is <= 200. So you can create a table which has c rows and m columns and dp on it.

[nymo]

I am trying DP. Can you give me some test cases... getting WAs. thanks.
[EDIT] stupid me... I 've found the error.

[joy]

I use DP, but can't understand why WA... plz give some I/O...

Code: Select all

ACC... :)

[nymo]

Joy, you can overwrite some positions in the following code fragment...

Code: Select all

for(j=0; j<=sum-m; j++)
               if(a[j]==i)
                  a[j+m]=i+1;

[joy]

thanks...
good problem

[sabir]

i am using dp but get wa.Give me some i/o.

[andmej]

i am using dp but get wa.Give me some i/o.

Try this input:

Code: Select all

7
100 4
3 8 6 4
2 5 10
4 1 3 3 7
4 50 14 23 8
20 3
3 4 6 8
2 5 10
4 1 3 5 5
5 3
3 6 4 8
2 10 6
4 7 3 1 7
6 3
2 1 2
2 3 5
2 1 0
200 3
2 100 100
2 97 99
3 2 4 1
20 3
3 4 6 8
2 5 10
4 1 3 5 6
200 20
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 181 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 180

Correct output is:

Code: Select all

75
19
no solution
6
200
20
200

[sabir]

Thnx andmej for ur I/O.My program give same output as your.But WA.Do u or any one else have more I/O ?

[andmej]

Post your code, I'll try to help you find your bug

[sabir]

i found error in my code.But now i am getting TLE.Plz help me.Here is my code

Code: Select all

#include <stdio.h>
#include <stdlib.h>

#define sz 30

long cost[sz][sz];
bool dup[sz][210],finish;
long type[sz],m,c,count,max;

void check(long node)
{
	long i,temp;

	node++;

	if(node==c)//last row
	{
		for(i=type[node]-1;i>=0;i--)
		{
			if(count+cost[node][i]<=m)
			{
				temp=count+cost[node][i];
				if(temp>max)
				{
					max=temp;
				}
			}
		}
	}

	for(i=type[node]-1;i>=0;i--)
	{
		if(count+cost[node][i]<=m)
		{
			count=count+cost[node][i];
			check(node);
			count=count-cost[node][i];
		}
	}
}

int main()
{

	long tcase,n,d,i,j,w,k;
	bool tag;

	scanf("%ld", &tcase);

	while(tcase--)
	{
		max=0;
		count=0;
		finish=false;

		scanf("%ld %ld", &m, &c);

		for(i=1;i<=c;i++)
		{
			scanf("%ld", &n);

			for(j=1,d=0;j<=n;j++)
			{
				scanf("%ld", &w);
				tag=true;

				for(k=0;k<d;k++)//check duplicate tata
				{
					if(cost[i][k]==w)
					{
						tag=false;
						break;
					}
				}
				if(tag==true)
				{
					cost[i][d]=w;
					d++;
				}
			}

			type[i]=d;//number column in ith row
			
		}

		for(i=0;i<type[1];i++)//first row
		{
			count=cost[1][i];
			check(1);
		}

		if(max==0)
		{
			printf("no solution\n");
		}
		else
		{
			printf("%ld\n", max);
		}

	}

	return 0;
}

[tryit1]

Code: Select all

10 3
1 1
2 2 2
1 10

Code: Select all

Output is
no solution

[Imti]

here are some cases for what my code failed,after fixing these I got accepted.. ..I'm posting these case here for them who are still struggling with it..

Code: Select all

4
4 3
2 2 2
2 1 1
2 1 3
4 3
2 2 2
2 1 1
2 3 1
6 3
2 2 5
2 2 4
2 2 3
7 3
2 1 5
2 3 3
2 2 4

Output:

Code: Select all

4
4
6
6

[ankush_kapoor]

i dont know why i am getting wa ,my code is passing all the inputs mentioned in the problem and in this forum.
heres my code sumone pls tell me whts wrong in it

Code: Select all

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int b,n,g[25][25],dp[210][30];
int rec(int budgetleft,int garment)
{
    if(garment==n)
        return 0;
    if(dp[garment][budgetleft]!=0)
    {
        return dp[garment][budgetleft];
    }
    int m=g[garment][0],flag=1;
    for(int i=1;i<=m;i++)
    {
        if(budgetleft-g[garment][i]>=0)
        {
            dp[garment][budgetleft]=max(dp[garment][budgetleft],rec(budgetleft-g[garment][i],garment+1)+g[garment][i]);
            if(dp[garment][budgetleft]>0)
                flag=0;
        }
    }
    if(flag==1)
    {
        return -1000000000;
    }

    return dp[garment][budgetleft];
}
int main()
{

    int t,maxi;
    scanf("%d",&t);
    while(t--)
    {
        for(int i=0;i<210;i++)
        {
            for(int j=0;j<30;j++)
                dp[i][j]=0;
        }
        scanf("%d%d",&b,&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&g[i][0]);
            {
                for(int j=1;j<=g[i][0];j++)
                {
                    scanf("%d",&g[i][j]);
                }
            }
        }
        maxi=rec(b,0);
        if(maxi<=0)
        {
            printf("no solution\n");
        }
        else
        {
            printf("%d\n",maxi);
        }
    }
    return 0;
}

[ankush_kapoor]

got acc silly mistake