10130 - SuperSale

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

Try this input:

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 · 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.

little joey · 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 · 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]

Timo · 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;
}

beloni · 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

beloni · 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

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

0-1 Knapsack problem => DP

mich · 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.

kbr_iut · 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/

mukit · 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.

emotional blind · 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 · 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.

mukit.

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

What are the other changes?

OJ Board

10130 - SuperSale

Thanks!

10130 wrong

10130 - SuperSales

10130 - SuperSales WA

Re: 10130 - SuperSales

Re: 10130 - SuperSales

Re: 10130 - SuperSales

Re: 10130 - SuperSales