## 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

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
try using Dynamic Programming, mbak Ing Ing. Brute Force is correct but sometimes gives TLE.
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### 10130

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
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
You're right.
The answer is 21.

Hope it helps.
Good Luck

Regards,
angga888
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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
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
Why the answer of sohel's input is 19? Could someone explain about it?
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
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
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
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
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

### 10130

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:
I can't solve this problem. Can you help me?? thanks
fpmc
New poster
Posts: 23
Joined: Tue Sep 30, 2003 11:44 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
Contact:

### 10130-can 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[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