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?