Page 1 of 1

### 11450 - Wedding shopping

Posted: Sun May 18, 2008 2:58 am
I think this problem can be solved using dynamic programming. However, I haven't been able to find the recurrent relation.

### Re: 11450 - Wedding shopping

Posted: Sun May 18, 2008 4:23 am
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.

### Re: 11450 - Wedding shopping

Posted: Fri Jun 27, 2008 10:28 pm
I am trying DP. Can you give me some test cases... getting WAs. thanks.
[EDIT] stupid me... I 've found the error.

### Re: 11450 - Wedding shopping

Posted: Thu Jul 03, 2008 10:45 pm
I use DP, but can't understand why WA... plz give some I/O...

Code: Select all

``````ACC... :)

``````

### Re: 11450 - Wedding shopping

Posted: Fri Jul 04, 2008 6:38 am
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;
``````

### Re: 11450 - Wedding shopping

Posted: Fri Jul 04, 2008 8:30 am
thanks...
good problem

### Re: 11450 - Wedding shopping

Posted: Sat Aug 09, 2008 8:52 pm
i am using dp but get wa.Give me some i/o.

### Re: 11450 - Wedding shopping

Posted: Sun Aug 10, 2008 12:21 am
sabir wrote: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
``````

### Re: 11450 - Wedding shopping

Posted: Mon Aug 11, 2008 8:41 pm
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 ?

### Re: 11450 - Wedding shopping

Posted: Tue Aug 12, 2008 3:28 am

### Re: 11450 - Wedding shopping

Posted: Thu Aug 14, 2008 9:06 pm
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;
}

``````

### Re: 11450 - Wedding shopping

Posted: Wed Sep 10, 2008 4:06 pm

Code: Select all

``````10 3
1 1
2 2 2
1 10

``````

Code: Select all

``````Output is
no solution
``````

### Re: 11450 - Wedding shopping

Posted: Tue May 03, 2011 12:18 pm
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
``````

### Re: 11450 - Wedding shopping

Posted: Sat Apr 18, 2015 5:06 pm
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;
}``````

### Re: 11450 - Wedding shopping

Posted: Sat Apr 18, 2015 5:17 pm
got acc silly mistake