## 10130 - SuperSale

Moderator: Board moderators

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Try this input:

Code: Select all

``````2
6
71 6
41 3
53 8
93 11
26 22
24 11
2
29
26
8
61 5
99 11
71 30
77 15
93 7
56 4
37 2
8 6
2
4
16
``````
The correct answers are 475 and 266, but your program gives 463 and 247.
475 = (71+41+53+93) + (71+53+93)
266 = (56) + (93+56+61)

Good luck. I ran a test of 10000 random cases and only those two were incorrect; your program handled the other 9998 cases ok. So you're on the right track.

sarah
New poster
Posts: 7
Joined: Tue Aug 30, 2005 2:54 pm
Location: Iran
Contact:

### Thanks!

AC at last!
Thanks for your help. I changed my algo, it was wrong but it didn't show
easily.
May I ask a question? How do you generate random inputs?
Thanks again.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
By using rand() from stdlib. For this problem I used:

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>

#define CASES 10000

int main(){
int caseno;
int n,p,w,g,mw;
int i;

printf("%d\n",CASES);
for(caseno=1;caseno<=CASES;caseno++){
n=1+rand()%10;
printf("%d\n",n);
for(i=0;i<n;i++){
p=1+rand()%100;
w=1+rand()%30;
printf("%d %d\n",p,w);
}
g=1+rand()%5;
printf("%d\n",g);
for(i=0;i<g;i++){
mw=1+rand()%30;
printf("%d\n",mw);
}
}
return 0;
}
``````
You also need a program that produces the correct answers, of course. But for this problem you could write a brute force solution that is too slow for the judge but is guaranteed to give correct answers.

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil

### 10130 wrong

hello
I'm with problems on a dynamic programming solution for the knapsack algorithm in this problem...
I think that my implementation ignores first input pair ( price, weight ) of all test cases ( as you can see by the printf( "%d\n", carry[num][maxw] ); at the end of dp_knapsack function )...
someone can tell me why ????

Code: Select all

``````#include <stdio.h>

#define NUM 1001
#define GROUP 101
#define MW 31

int max( int x, int y )
{
return (x > y) ? x : y;
}

int dp_knapsack( const int *p, const int *wi, const int num, const int maxw )
{
int carry[NUM][MW], i, w;

for( i = 0; i <= num; i++ )
carry[i] = 0;
for( w = 0; w <= maxw; w++ )
carry[w] = 0;

for( i = 1; i <= num; i++ )
for( w = 1; w <= maxw; w++ )
{
if( wi[i] >= w )
carry[i][w] = carry[i-1][w];
else
carry[i][w] = max( carry[i-1][w], carry[i-1][w-wi[i]] + p[i] );
}

printf( "%d\n", carry[num][maxw] );

return carry[num][maxw];
}

int main()
{
int no, ng, tcases, i, total;
int price[NUM], weight[NUM], maxw;

scanf( "%d", &tcases );
while( tcases-- )
{
total = 0;
scanf( "%d", &no );

for( i = 0; i < no; i++ )
scanf( "%d %d", &price[i], &weight[i] );

scanf( "%d", &ng );
for( i = 0; i < ng; i++ )
{
scanf( "%d", &maxw );
total += dp_knapsack( price, weight, no, maxw );
}
printf( "total: %d\n", total );
}

return 0;
}
``````
thanks[/quote]
"A machine can do the work of fifty ordinary men, but no machine can do the work of one extraordinary man.", Shahriar Manzoor

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia
Your DP algo for knapsack problem is same with me, but I think you should call it once.After that you can use the table many times.

I have change part of your code, this one should give AC.

Code: Select all

``````#include <stdio.h>

#define NUM 1001
#define GROUP 101
#define MW 31

int carry[NUM][MW];
int p[NUM], wi[NUM];

int max( int x, int y )
{
return (x > y) ? x : y;
}

void dp_knapsack(int num)
{
int  i, w;

for( i = 0; i <= num; i++ )
carry[i] = 0;
for( w = 0; w < MW; w++ )
carry[w] = 0;

for( i = 1; i <= num; i++ )
for( w = 1; w < MW; w++ )
{
if( wi[i] > w )
carry[i][w] = carry[i-1][w];
else
carry[i][w] = max( carry[i-1][w], carry[i-1][w-wi[i]] + p[i] );
}
}

int main()
{
int no, ng, tcases, i, total;
int  maxw;

scanf( "%d", &tcases );
while( tcases-- )
{
total = 0;
scanf( "%d", &no );

for( i = 1; i <= no; i++ )
scanf( "%d %d", &p[i], &wi[i] );

dp_knapsack(no);
scanf( "%d", &ng );
for( i = 0; i < ng; i++ )
{
scanf( "%d", &maxw );
total += carry[no][maxw];
}
printf( "%d\n", total );
}

return 0;
}          ``````
"Life is more beautiful with algorithm"

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil
ok, thanks
but I still get WA... can you give me sample input ???
other question: why the for( i = 1; i <= no; i++ ) must be on interval [1..no] instead [0..no[ ???

thanks for help
"A machine can do the work of fifty ordinary men, but no machine can do the work of one extraordinary man.", Shahriar Manzoor

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil
I'm sorry...
I was writed the code wrong really a stupid mistake

buts keeps the question: why the for( i = 1; i <= no; i++ ) must be on interval [1..no] instead [0..no[ ???

thanks ans I'm so sorry "A machine can do the work of fifty ordinary men, but no machine can do the work of one extraordinary man.", Shahriar Manzoor

mich
New poster
Posts: 3
Joined: Sun Jun 04, 2006 9:16 pm

### 10130 - SuperSales

Hi,

I am getting TLE on problem 10130.

Here is the code for my function calculating the max each person can buy (works fine on the sample test cases).

Code: Select all

``````int best(int w, int i1) {
int t = 0;
if(cache[w][i1] != -1) return cache[w][i1];
for(int i = i1; i < 1000; i++) {
if(o1[i] == -1) break;
if( (w-o2[i]) >= 0) {
t = max( best(w-o2[i], i+1)+o1[i], t);
}

}
cache[w][i1]=t;
return t;
}``````
Could anyone explain what I am doing wrong -- what is inefficient that I am getting TLE? Is recursion too slow?

Thanks.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
0-1 Knapsack problem => DP
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

mich
New poster
Posts: 3
Joined: Sun Jun 04, 2006 9:16 pm
Yes, I know it is a 0-1 knapsack problem, my function does just that, just that I am using recursion(with memoization) instead of DP.

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

### 10130 - SuperSales WA

can ne1 tell me whats wrong with this code.it works well for all inputs of board.

Code: Select all

``````#include<stdio.h>
#define max 10100
long m[max],N,W[max],V[max];
void knapsack(){
int i,w;
for(i=0;i<=N;i++)m[i]=0;
for(i=0;i<=35;i++)m[i]=0;
for(i=1;i<=35;i++){
for(w=1;w<=35;w++){
if(w<W[i])m[i][w]=m[i-1][w];
else{
if(m[i-1][w]>=V[i]+m[i-1][w-W[i]])m[i][w]=m[i-1][w];
else m[i][w]=V[i]+m[i-1][w-W[i]];
}
}
}
}
int main(){
int i,num,T,person,amount;
//freopen("10130.txt","r",stdin);
//freopen("output.txt","w",stdout);
scanf("%d",&T);
while(T--){
scanf("%d",&N);
for(i=1;i<=N;i++)scanf("%d%d",&V[i],&W[i]);
knapsack();
scanf("%d",&num);
amount=0;
while(num--){
scanf("%d",&person);
amount+=m[N][person];
}
printf("%d\n",amount);
}
return 0;
}

``````
i generated inputs randomly and those r correct according to the site http://uvatoolkit.com/
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

mukit
New poster
Posts: 48
Joined: Wed Nov 21, 2007 10:09 am
Contact:

### Re: 10130 - SuperSales

Hi , I'm getting W.A in this problem with a running time of 1.65s.

Code: Select all

``````Removed.
``````
mukit.
Last edited by mukit on Thu Feb 12, 2009 1:58 pm, edited 1 time in total.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:

### Re: 10130 - SuperSales

Code: Select all

``````   if(memo[n][wa]!=-1)return memo[n][wa];
if(n<0 || wa<=0)return 0;``````
This two lines should be swapped.

mukit
New poster
Posts: 48
Joined: Wed Nov 21, 2007 10:09 am
Contact:

### Re: 10130 - SuperSales

Thank's emotional blind. I edited as you said and a little bit of mine. Got AC with 0.080s runtime. mukit.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am