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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Oct 26, 2005 12:16 am

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!

Post by sarah » Sat Oct 29, 2005 8:22 am

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Oct 29, 2005 9:51 am

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

Post by beloni » Mon Apr 24, 2006 10:55 pm

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]
"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

Post by Timo » Tue Apr 25, 2006 5:00 am

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;
}          
"Life is more beautiful with algorithm"

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

Post by beloni » Tue Apr 25, 2006 7:34 pm

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

Post by beloni » Tue Apr 25, 2006 7:58 pm

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 :oops:
"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

Post by mich » Mon Jun 05, 2006 9:41 pm

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

Post by serur » Mon Jun 05, 2006 10:03 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

Post by mich » Mon Jun 05, 2006 10:11 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.

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

10130 - SuperSales WA

Post by kbr_iut » Wed Aug 13, 2008 2:44 am

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/
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
Location: Dhaka , Bangladesh
Contact:

Re: 10130 - SuperSales

Post by mukit » Wed Feb 11, 2009 7:19 pm

Hi , I'm getting W.A in this problem with a running time of 1.65s.
Please give some I/O.

Code: Select all

Removed.
Thank's in advance.
mukit.
Last edited by mukit on Thu Feb 12, 2009 1:58 pm, edited 1 time in total.

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

Re: 10130 - SuperSales

Post by emotional blind » Thu Feb 12, 2009 1:00 pm

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
Location: Dhaka , Bangladesh
Contact:

Re: 10130 - SuperSales

Post by mukit » Thu Feb 12, 2009 2:04 pm

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

mukit.

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

Re: 10130 - SuperSales

Post by emotional blind » Thu Feb 12, 2009 7:37 pm

What are the other changes?

Post Reply

Return to “Volume 101 (10100-10199)”