10130 - SuperSale

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

10130 - SuperSale

Post by b3yours3lf » Wed Apr 23, 2003 11:36 am

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?

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Thu Apr 24, 2003 5:02 am

try using Dynamic Programming, mbak Ing Ing. Brute Force is correct but sometimes gives TLE.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

10130

Post by sohel » Sat Dec 06, 2003 3:53 pm

I used 0/1 knapsack.
But I am getting WA.
Can someone give me some critical inputs? :(

What is the output for
1
5
1 5
2 4
3 3
4 2
5 1
2
6
5

Is it:
21

Another question: is there infinite supply of each product.
Thanx :)

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Tue Dec 23, 2003 8:03 am

You're right.
The answer is 21.

Hope it helps.
Good Luck :D

Regards,
angga888

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Tue Dec 23, 2003 8:28 am

Finally Got AC.
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.

salutte
New poster
Posts: 1
Joined: Fri Mar 26, 2004 11:44 pm

Post by salutte » Mon Apr 19, 2004 12:33 pm

I 'm also getting WA with this problem, can you post your "stupid mistake"?

It's possible that i made the same mistake!!

I don't know what could go wrong!

Thanks!

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl » Sun Jun 20, 2004 9:46 am

Why the answer of sohel's input is 19? Could someone explain about it?

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Sun Jun 20, 2004 10:56 am

htl wrote:Why the answer of sohel's input is 19?
Which one? Do you mean the input in the first post here? If yes, the answer is not 19, but 21.

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl » Mon Jun 21, 2004 2:48 pm

Sorry, it's my mistake. 19 is my answer. But I still don't know how you can get 21 as answer?

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

Post by jackie » Sat Jul 17, 2004 12:25 pm

First person :
5 1
4 2
3 3
1 + 2 + 3 = 6 <= 6
5 + 4 + 3 = 12
so first person can take three objects and the maximal value is 12

Second person:
5 1
4 2
1 + 2 = 3 <= 5
5 + 4 = 9
so second person can take tow objects and the maximal value is 9

Finally the answer is 21.

I use DP Knapstack, but not very efficient AC in 1.1 sec

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

10130

Post by jagadish » Mon Aug 02, 2004 8:01 am

Can someone tell me how to modify the classical 0/1knapsack to handle multiple knapsacks ?

conantth
New poster
Posts: 3
Joined: Sat Jun 05, 2004 6:22 pm
Contact:

Post by conantth » Mon Aug 02, 2004 1:22 pm

I can't solve this problem. Can you help me?? thanks

fpmc
New poster
Posts: 23
Joined: Tue Sep 30, 2003 11:44 pm

Post by fpmc » Tue Aug 24, 2004 1:35 pm

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 0-1 Knapsack G times and report the sum

Frank

backbencher
New poster
Posts: 5
Joined: Thu Sep 23, 2004 12:10 am
Location: Bangladesh
Contact:

10130-can anyone help?

Post by backbencher » Thu Sep 23, 2004 12:51 am

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[k-1]<=m)
{
if(k<n)
bknap(k+1,cp+p[k-1],cw+w[k-1],p,w,n,m);
if(cp+p[k-1]>fp&&k==n)
{
fp=cp+p[k-1];
fw=cw+w[k-1];
}
}
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]

backbencher
New poster
Posts: 5
Joined: Thu Sep 23, 2004 12:10 am
Location: Bangladesh
Contact:

sorry

Post by backbencher » Thu Sep 23, 2004 1:06 am

sorry i've made a mistake

no need to bother with my code

Post Reply

Return to “Volume 101 (10100-10199)”