10130 - SuperSale

[b3yours3lf]

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]

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

[sohel]

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]

You're right.
The answer is 21.

Hope it helps.
Good Luck

Regards,
angga888

[sohel]

Finally Got AC.
I made a stupid mistake.

Nevertheless,
Thanks Angga.

[salutte]

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]

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

[angga888]

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]

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

[jackie]

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]

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

[conantth]

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

[fpmc]

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]

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]

sorry i've made a mistake

no need to bother with my code