10130 - SuperSale
Moderator: Board moderators
Re: 10130 - SuperSales
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.
mukit.
Keep posting emotional blind. You are really helpful.
mukit.
-
- Learning poster
- Posts: 97
- Joined: Fri Aug 22, 2008 10:18 pm
- Location: CSE.SUST.SYLHET
Re: 10130 - SuperSales
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.
Re: 10130 - SuperSales
I do not know why it give me run time error
this is my code
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;
}
Re: 10130 - SuperSales
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!
regards
sauro
regards
sauro
all that we see or seem is but a dream within a dream
-
- New poster
- Posts: 4
- Joined: Fri Dec 17, 2010 8:28 am
Re: 10130 - SuperSales
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
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
-
- New poster
- Posts: 1
- Joined: Fri Mar 18, 2011 11:05 am
Re: 10130 - SuperSales
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;
}
-
- New poster
- Posts: 1
- Joined: Fri Aug 31, 2012 1:06 pm
Re: 10130 - SuperSales
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;
}
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;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10130 - SuperSales
Try solving it without using recursion.
Check input and AC output for thousands of problems on uDebug!
super sale problem is WA
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;
}
#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;
}
Re: super sale problem is WA
please any one reply me because i get tired of this problem
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: super sale problem is WA
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
Your code doesn't match the sample I/O.
https://ideone.com/3spnI
Check input and AC output for thousands of problems on uDebug!
-
- New poster
- Posts: 1
- Joined: Fri Sep 07, 2012 7:36 pm
10130 Super Sale .. always TLE ?! :(
Hello .. My Code Always Gets TLE in UVA
Can any one help me ?
My Code : http://pastebin.com/T4i79giL
Can any one help me ?
My Code : http://pastebin.com/T4i79giL
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10130 Super Sale .. always TLE ?! :(
Try solving it without using recursion.
Check input and AC output for thousands of problems on uDebug!
Re: super sale problem is WA
check your code with an empty string for an input, you need to read the input line by line.
jimmight
Re: 10130 Super Sale .. always TLE ?! :(
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
http://en.wikipedia.org/wiki/Knapsack_problem
try that, and I can help you on your DP code