10130  SuperSale
Moderator: Board moderators

 New poster
 Posts: 44
 Joined: Wed Aug 14, 2002 3:02 am
10130  SuperSale
I have tried this problem and I got TLE.
My program use recursive to test all combination.
Is there any way to solve this problem?
My program use recursive to test all combination.
Is there any way to solve this problem?

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut
Finally Got AC.
I made a stupid mistake.
Nevertheless,
Thanks Angga.
I made a stupid mistake.
Nevertheless,
Thanks Angga.
Last edited by sohel on Tue Apr 20, 2004 6:34 am, edited 1 time in total.
First person :
Second person:
Finally the answer is 21.
I use DP Knapstack, but not very efficient AC in 1.1 sec
so first person can take three objects and the maximal value is 125 1
4 2
3 3
1 + 2 + 3 = 6 <= 6
5 + 4 + 3 = 12
Second person:
so second person can take tow objects and the maximal value is 95 1
4 2
1 + 2 = 3 <= 5
5 + 4 = 9
Finally the answer is 21.
I use DP Knapstack, but not very efficient AC in 1.1 sec
The problem is badly worded.
There are N types of objects, each with a value and a weight, and there are G people, each with a capacity. Each person can take at most one object from each type, but can take as many objects as one can carry. Find the maximal value that the G people can carry out.
In short: Run 01 Knapsack G times and report the sum
Frank
There are N types of objects, each with a value and a weight, and there are G people, each with a capacity. Each person can take at most one object from each type, but can take as many objects as one can carry. Find the maximal value that the G people can carry out.
In short: Run 01 Knapsack G times and report the sum
Frank

 New poster
 Posts: 5
 Joined: Thu Sep 23, 2004 12:10 am
 Location: Bangladesh
 Contact:
10130can anyone help?
Some body pls give me some critical input
I m tired of getting WA on 10130
why this code gives WA:
(Please ignore the code if it tires u)
long bknap(long k,long cp,long cw,long p[],long w[],long n,long m);
long bound(long cp,long cw,long k,long n,long m,long p[],long w[]);
long fp,fw;
void main()
{
long i,W[1000],P[1000],m[100],N,G;
long total,test;
cin>>test;
while(test>0)
{
test;
cin>>N;
for(i=0;i<N;i++)
cin>>P[i]>>W[i];
cin>>G;
for(i=0;i<G;i++)
cin>>m[i];
total=0;
for(i=0;i<G;i++)
{
fp=0;fw=0;
total+=bknap(1,0,0,P,W,N,m[i]);
}
cout<<total<<"\n";
}
}
long bound(long cp,long cw,long k,long n,long m,long p[],long w[])
{
long i,c,b=cp;
c=cw;
for(i=k;i<n;i++)
{
c=c+w[i];
if(c<=m)
b=b+p[i];
else
return b;
}
return b;
}
long bknap(long k,long cp,long cw,long p[],long w[],long n,long m)
{
if(cw+w[k1]<=m)
{
if(k<n)
bknap(k+1,cp+p[k1],cw+w[k1],p,w,n,m);
if(cp+p[k1]>fp&&k==n)
{
fp=cp+p[k1];
fw=cw+w[k1];
}
}
if(bound(cp,cw,k,n,m,p,w)>=fp)
{
if(k<n)bknap(k+1,cp,cw,p,w,n,m);
if(cp>fp&&k==n)
{
fp=cp;fw=cw;
}
}
return fp;
}
[/quote][/list][/cpp]
I m tired of getting WA on 10130
why this code gives WA:
(Please ignore the code if it tires u)
long bknap(long k,long cp,long cw,long p[],long w[],long n,long m);
long bound(long cp,long cw,long k,long n,long m,long p[],long w[]);
long fp,fw;
void main()
{
long i,W[1000],P[1000],m[100],N,G;
long total,test;
cin>>test;
while(test>0)
{
test;
cin>>N;
for(i=0;i<N;i++)
cin>>P[i]>>W[i];
cin>>G;
for(i=0;i<G;i++)
cin>>m[i];
total=0;
for(i=0;i<G;i++)
{
fp=0;fw=0;
total+=bknap(1,0,0,P,W,N,m[i]);
}
cout<<total<<"\n";
}
}
long bound(long cp,long cw,long k,long n,long m,long p[],long w[])
{
long i,c,b=cp;
c=cw;
for(i=k;i<n;i++)
{
c=c+w[i];
if(c<=m)
b=b+p[i];
else
return b;
}
return b;
}
long bknap(long k,long cp,long cw,long p[],long w[],long n,long m)
{
if(cw+w[k1]<=m)
{
if(k<n)
bknap(k+1,cp+p[k1],cw+w[k1],p,w,n,m);
if(cp+p[k1]>fp&&k==n)
{
fp=cp+p[k1];
fw=cw+w[k1];
}
}
if(bound(cp,cw,k,n,m,p,w)>=fp)
{
if(k<n)bknap(k+1,cp,cw,p,w,n,m);
if(cp>fp&&k==n)
{
fp=cp;fw=cw;
}
}
return fp;
}
[/quote][/list][/cpp]

 New poster
 Posts: 5
 Joined: Thu Sep 23, 2004 12:10 am
 Location: Bangladesh
 Contact:
sorry
sorry i've made a mistake
no need to bother with my code
no need to bother with my code