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

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

Re: 10130 - SuperSales

Post by mukit » Tue Feb 17, 2009 9:02 pm

First time, i set the memo[][] with -1 prior taking each persons input (total G times for each case). Later ,I did that prior taking all persons input (total 1 time for each case). Thus got a far better runtime. :) .This was the "other change". I was only getting WA for the fact you said. And with "other change" it became faster.

Keep posting emotional blind. You are really helpful. :D

mukit.

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Re: 10130 - SuperSales

Post by saiful_sust » Tue Jun 02, 2009 11:22 pm

HI Every one.
I solve this problem with knapsack
but i want to make it faster can any one tell me how can i do this.
:-?

Daliash
New poster
Posts: 1
Joined: Thu Dec 03, 2009 10:29 am

Re: 10130 - SuperSales

Post by Daliash » Thu Dec 03, 2009 10:37 am

I do not know why it give me run time error :( :( :(
this is my code

Code: Select all

# include <iostream>
//#include <fstream>

using namespace std;


int MAX( int X, int Y )
{
	if ( X>Y )
		return X;
	else return Y;

}
int  Knapsack(int  WeightOfPerson,int WeightOfObiects[] ,int  PriceOfobject[], int NumberOfObjects )
{
	int KSTable[30][1000]={0};
		for (int i=0; i<=WeightOfPerson ;i++)
			for (int j=1; j<=NumberOfObjects  ;j++)
			{
				if ( WeightOfObiects[j-1]> i)
					KSTable[i][j]=KSTable[i][j-1];
				else
				{
					KSTable[i][j]=MAX ( KSTable[i][j-1], KSTable[i-WeightOfObiects [j-1]][j-1]+PriceOfobject [j-1]);

				}
			
			
			}

return KSTable[WeightOfPerson][NumberOfObjects ];
}

//# define cin fin 

int main()
{
	/*ifstream fin;
	fin.open("input.txt");*/

	int NumberOfCases, NumberOfObjects,NumberOfPersons, MaxValueOfObjecs=0;
	int PriceOfobject[1000]={0};
	int WeightOfObiects[1000]={0};

	int WeightOfPersons[100]={0};
	cin >> NumberOfCases;
	for (int MM=0; MM<NumberOfCases ;MM++)
	{	
			cin >> NumberOfObjects;
			for (int j=0; j<NumberOfObjects ;j++)
			{
				cin >> PriceOfobject[j];
				cin >> WeightOfObiects[j];
			}

			cin>> NumberOfPersons ;
			for (int j=0; j<NumberOfPersons ;j++)
			{
				cin >> WeightOfPersons[j];
			}

			//Sort
			

			  int key,i,key1;
			  for(int j=1;j<NumberOfObjects ;j++)
			  {
				 key=WeightOfObiects [j];
				 key1= PriceOfobject [j];
				 i=j-1;
				 while(WeightOfObiects [i]>key && i>=0)
				 {
						   WeightOfObiects [i+1]=WeightOfObiects [i];
						    PriceOfobject [i+1]=PriceOfobject[i];

					 i--;
				 }
				 WeightOfObiects [i+1]=key;
				 PriceOfobject [i+1]=key1;

			  }


	
			   for(int j=0;j<NumberOfPersons  ;j++)
			   {
				   MaxValueOfObjecs+= Knapsack(WeightOfPersons[j],WeightOfObiects , PriceOfobject, NumberOfObjects);
			   
			   }

	
				cout<< MaxValueOfObjecs<<endl;
				MaxValueOfObjecs=0;
	
	}



return 0;
}



sauro
New poster
Posts: 4
Joined: Mon Aug 30, 2010 11:26 pm
Location: BUET, bangladesh
Contact:

Re: 10130 - SuperSales

Post by sauro » Fri Nov 12, 2010 9:15 am

some people are running the knapsack DP G times which is eventually slowing down their program. for each case, you should run the the DP only once for that person who has the highest maximal weight. the others will be solved as a sub-problem! it only took me 0.028 secs! :wink:

regards
sauro
all that we see or seem is but a dream within a dream

justcodeit
New poster
Posts: 4
Joined: Fri Dec 17, 2010 8:28 am

Re: 10130 - SuperSales

Post by justcodeit » Fri Dec 17, 2010 8:30 am

Hello.....
in this question i m confused with the last part of the questions.....

"Next line contains one integer (1<=G<=100) it’s the number of people in our group. Next G lines contains maximal weight (1<=MW<=30) that can stand this i-th person from our family (1<=i<=G)."

what we need to do with this.......
:(

PLease help.......
thanks

nhrahi_iut
New poster
Posts: 1
Joined: Fri Mar 18, 2011 11:05 am

Re: 10130 - SuperSales

Post by nhrahi_iut » Fri Mar 18, 2011 11:11 am

Can please somebody help me with the code,it is getting run time error but i cant find out why?????

Code: Select all

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int value[150],weight[150],C[50][50],N,W;

int knapsack(int N,int W){
    int i,w,temp;
 //   memset(C,0,sizeof C);
    for(i=1 ; i<=N ; i++) C[i][0]=0;
    for(w=0 ; w<=W ; w++) C[0][w]=0;

    for(i=0 ; i<=N ; i++)
        for(w=1 ; w<=W ; w++){
            if (weight[i] > w)
                C[i][w] = C[i-1][w];
              else
                C[i][w] = max(C[i-1][w] , C[i-1][w-weight[i]]+value[i]);
        }
        temp=C[N][W];
//        cout<<temp<<endl;
   return temp;
}

int main(){
    int TC,person;
//    freopen("10130.txt","r",stdin);
    while(scanf("%d",&TC)==1){
         while(TC--){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        scanf("%d %d",&value[i],&weight[i]);
    }
    scanf("%d",&person);
    int total=0,sum;
    for(int i=0;i<person;i++){
            scanf("%d",&W);
            sum=knapsack(N,W);
            total = total + sum;
            }
     cout<<total<<endl;
        }
    }
    return 0;
}

hossam yosef
New poster
Posts: 1
Joined: Fri Aug 31, 2012 1:06 pm

Re: 10130 - SuperSales

Post by hossam yosef » Fri Aug 31, 2012 1:21 pm

TLE... can anyone help me :@

code:
#include <iostream>
#include <string>
#include <climits>
#include <algorithm>
using namespace std;

int weight[1000+10];
int prize[1000+10];
int dp[1000+10][40];

int n, res;
int ww, num;
int maX(int index, int w, int p)
{

if(index == n)
{
if(w <= ww)
return dp[index][w] = p;
else
return dp[index][w] = INT_MIN;
}

return dp[index][w] = max(maX(index+1, w + weight[index], p + prize[index]), maX(index+1, w, p));

}

int main()
{
int T;
cin >> T;
while(T--){
cin >> n;
for(int i = 0; i < n; i++)
cin >> prize >> weight;

cin >> num;
res = 0;
for (int i = 0; i < 1010; i++)
for(int j = 0; j < 35; j++)
dp[j] = -1;
for(int ii = 0; ii < num; ii++){

cin >> ww;
res += maX(0, 0, 0);

}
cout << res << endl;
}
return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10130 - SuperSales

Post by brianfry713 » Fri Aug 31, 2012 7:37 pm

Try solving it without using recursion.
Check input and AC output for thousands of problems on uDebug!

emo
New poster
Posts: 4
Joined: Sun Sep 02, 2012 10:50 pm

super sale problem is WA

Post by emo » Sun Sep 02, 2012 11:04 pm

:( hello please i need help this problem is WA but i don't know why and i tried the input the output was correct but in uva is WA this is my code:
#include<iostream>
#include<string>
using namespace std;
int weights[1005],num_person;
int prices[1005],person_max;int takeItem, skipItem;;
int waight,price,num,sum=0,arr[1005][35];
int solve(int index, int weight)
{

if(arr[index][weight]!=-1)
return arr[index][weight];
if(index==num)
{
if(weight <= person_max)
{
return arr[index][weight]=price;

}
else
return arr[index][weight]= 0;
}
int takeItem, skipItem;
if(weight+weights[index]<=person_max)
{
takeItem = solve(index + 1, weight + weights[index])+ price + prices[index];
}
skipItem = solve(index + 1, weight);
return arr[index][weight]=max(takeItem, skipItem);
}
int main()
{
int testCases;
cin>>testCases;
for(int i=0;i<testCases;i++)
{
cin>>num;
for(int j=0;j<num;j++)
{
cin>>prices[j]>>weights[j];
}
cin>>num_person;
for(int j=0;j<num_person;j++)
{
cin>>person_max;
for(int k=0;k<1005;k++)
for(int l=0;l<35;l++)
arr[k][l]=-1;
sum+= solve(0, 0);
}
cout<<sum << endl;
sum=0;
}
return 0;
}

emo
New poster
Posts: 4
Joined: Sun Sep 02, 2012 10:50 pm

Re: super sale problem is WA

Post by emo » Sun Sep 02, 2012 11:23 pm

please any one reply me because i get tired of this problem :(

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: super sale problem is WA

Post by brianfry713 » Tue Sep 04, 2012 8:49 pm

Next time list the problem number 10130, post to the existing thread http://acm.uva.es/board/viewtopic.php?t=10850, and use the code blocks.

Your code doesn't match the sample I/O.
https://ideone.com/3spnI
Check input and AC output for thousands of problems on uDebug!

shadowguns
New poster
Posts: 1
Joined: Fri Sep 07, 2012 7:36 pm

10130 Super Sale .. always TLE ?! :(

Post by shadowguns » Fri Sep 07, 2012 7:41 pm

Hello .. My Code Always Gets TLE in UVA :( :(
Can any one help me ? :(
My Code : http://pastebin.com/T4i79giL

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10130 Super Sale .. always TLE ?! :(

Post by brianfry713 » Mon Sep 10, 2012 10:30 pm

Try solving it without using recursion.
Check input and AC output for thousands of problems on uDebug!

mikhelee
New poster
Posts: 1
Joined: Wed Sep 12, 2012 6:26 am

Re: super sale problem is WA

Post by mikhelee » Wed Sep 12, 2012 6:29 am

check your code with an empty string for an input, you need to read the input line by line.
jimmight

rrodrigoa
New poster
Posts: 1
Joined: Sat Dec 01, 2012 9:25 pm

Re: 10130 Super Sale .. always TLE ?! :(

Post by rrodrigoa » Sat Dec 01, 2012 11:35 pm

Take a look at the following link for creating a DP of your sale function
http://en.wikipedia.org/wiki/Knapsack_problem

try that, and I can help you on your DP code

Post Reply

Return to “Volume 101 (10100-10199)”