Page **3** of **6**

Posted: **Wed Oct 26, 2005 12:16 am**

by **little joey**

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.

### Thanks!

Posted: **Sat Oct 29, 2005 8:22 am**

by **sarah**

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.

Posted: **Sat Oct 29, 2005 9:51 am**

by **little joey**

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.

### 10130 wrong

Posted: **Mon Apr 24, 2006 10:55 pm**

by **beloni**

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] = 0;
for( w = 0; w <= maxw; w++ )
carry[0][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]

Posted: **Tue Apr 25, 2006 5:00 am**

by **Timo**

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 can't help you to find where is your fault, but I assured your DP algo is right.

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] = 0;
for( w = 0; w < MW; w++ )
carry[0][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;
}
```

Posted: **Tue Apr 25, 2006 7:34 pm**

by **beloni**

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

Posted: **Tue Apr 25, 2006 7:58 pm**

by **beloni**

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

### 10130 - SuperSales

Posted: **Mon Jun 05, 2006 9:41 pm**

by **mich**

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.

Posted: **Mon Jun 05, 2006 10:03 pm**

by **serur**

0-1 Knapsack problem => DP

Posted: **Mon Jun 05, 2006 10:11 pm**

by **mich**

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.

### 10130 - SuperSales WA

Posted: **Wed Aug 13, 2008 2:44 am**

by **kbr_iut**

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][100],N,W[max],V[max];
void knapsack(){
int i,w;
for(i=0;i<=N;i++)m[i][0]=0;
for(i=0;i<=35;i++)m[0][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/

### Re: 10130 - SuperSales

Posted: **Wed Feb 11, 2009 7:19 pm**

by **mukit**

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

Please give some I/O.

Thank's in advance.

mukit.

### Re: 10130 - SuperSales

Posted: **Thu Feb 12, 2009 1:00 pm**

by **emotional blind**

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.

### Re: 10130 - SuperSales

Posted: **Thu Feb 12, 2009 2:04 pm**

by **mukit**

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

mukit.

### Re: 10130 - SuperSales

Posted: **Thu Feb 12, 2009 7:37 pm**

by **emotional blind**

What are the other changes?