Page 5 of 6

### Re: 10130 - SuperSales

Posted: Sat Feb 09, 2013 8:08 pm
seem to have a runtime error (again) I also cannot compile it using g++.
Anyway, could someone help to debug? I am relatively new to DP. Also, can someone tell me how to make this run faster (if it does run at all).

Code: Select all

``````#include <iostream>
using namespace std;

int main(){
int T,N,G,P[100],W[30],F[30],max,ans,a1,a2,a3;
/*
T = test cases, N = number of objects, G = number of people
P = price, W = weight, F = family members, m = maximum capacity
ans = maximum value within capacity of the whole family
a1,a2... = temp integers
*/
cin>>T;
for(a1=0;a1<T;a1++){
max=ans=0;
cin>>N;
for(a2=0;a2<N;a2++){
cin>>P[a2]>>W[a2];
}
cin>>G;
for(a2=0;a2<G;a2++){
cin>>F[a2];
if(F[a2]>max)max=F[a2];
}
// adapted from wikipedia. method = dynamic programming
int m[N+1][max+1];
for(a2=1;a2<=max;a2++){
m[0][a2]=0;
}
for(a2=1;a2<=N;a2++){
for(a3=1;a3<=max;a3++){
if(a3>=W[a2-1]){
m[a2-1][a3]>m[a2-1][a3-W[a3-1]]?m[a2][a3]=m[a2-1][a3]:m[a2][a3]=m[a2-1][a3-W[a3-1]];
}else{
m[a2][a3]=m[a2-1][a3];
}
}
}
for(a2=0;a2<G;a2++){
ans+=m[N][F[a2]];
}
cout<<ans<<endl;
}
}``````

### Re: 10130 - SuperSales

Posted: Mon Feb 11, 2013 4:04 pm
Below is my code. No idea why get wa. pls help :

Code: Select all

``````#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
int n, g, sum = 0;
int p[105],w[105];
int dp[1004][35];// num of object and weight left

int knapsack(int resourcel, int item){
//if(resourcel < 0) return (1<<31);
if(item == n) return 0;
if(resourcel == 0) return 0;
if(dp[item][resourcel] != -1) return dp[item][resourcel];

if(resourcel - w[item] < 0){
dp[item][resourcel]  = knapsack(resourcel,item+1);
return dp[item][resourcel];
}
else{
int take = knapsack(resourcel - w[item],item+1) + p[item];
int notTake = knapsack(resourcel,item+1);
dp[item][resourcel] = take > notTake?take : notTake;
return dp[item][resourcel];
}

}
int main(){
int tc,dummy;
//freopen("in.txt","r",stdin);
scanf("%d",&tc);
for(int i = 0 ; i < tc; i++){
sum  = 0;
memset(dp,-1,sizeof(dp));
scanf("%d",&n);

for(int j = 0 ; j < n ;j++){
scanf("%d %d",&p[j],&w[j]);

}
scanf("%d",&g);

for(int i = 0 ; i< g;i++){
scanf("%d",&dummy);
sum+= knapsack(dummy,0);//wight allowed and item visited
}
printf("%d\n",sum);

}

return 0;

}``````

### Re: 10130 - SuperSales

Posted: Mon Feb 11, 2013 9:07 pm
For hover1178
maximum item is 1 <= N <= 1000... Now see that int p[105],w[105];...Hope that its help you .

### Re: 10130 - SuperSales

Posted: Tue Feb 12, 2013 9:37 pm
Safio, your code compiles fine for me. On the sample input, I get a seg fault on line 32 when a3=17 and W[a3-1]=-1073755656

### Re: 10130 - SuperSales

Posted: Sat Dec 07, 2013 7:14 pm
i'm getting RE !!!!!, but my code runs normally at VS 2012 and idone.com !!
any help?

Code: Select all

``````//AC :D, just had to double check my DP [][] ranges :D
``````

### Re: super sale problem is WA

Posted: Tue Mar 11, 2014 10:09 am
Yes, man this seems to be a code issue. There is some wrong string included which is blocking you in getting the right answer. I guess you can check with any moderators and get their help to correct the code.

Thanks
LOURENE

### Re: 10130 - SuperSales

Posted: Sat Jul 12, 2014 3:21 pm
I keep getting RE, but it runs normally in my computer. Can anyone please help.?

Code: Select all

``````#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int keep[150][40];

int prices[1010];
int weight[1010];

int main()
{
int T;
cin>> T;

for(int i=0; i<T; i++)
{
int objects;
int sum=0;
cin >> objects;

for(int j=1; j<=objects; ++j)
{
cin >> prices[j] >> weight[j];
}
int g;
cin>> g;
int max_weight[120];

for(int k=0; k<g; ++k)
{
cin >> max_weight[k];
}
for(int m=0; m<=objects; ++m) // For every item
{
for(int n=0; n<30; ++n) // For every weight
{
if(m==0){keep[m][n]=0;} // If it is the top row initialize to zero
else // If not
{
if(weight[m]<=n) // If weight of item is greater than the total weight we have
{
keep[m][n]=max(keep[m-1][n], prices[m]+keep[m-1][n-weight[m]]);
}
else
{
keep[m][n]=keep[m-1][n];
}
}
}
}
for(int p=0; p<g; p++)
{
sum+=keep[objects][max_weight[p]];
}
cout << sum << endl;
}
return 0;
}
``````

### Re: 10130 - SuperSales

Posted: Sat Jul 12, 2014 6:12 pm
You must increase first paramater

Code: Select all

``int keep[150][40];``
It must be

Code: Select all

``int keep[1010][40];``
Because you use it with variable m

Code: Select all

``keep[m][n]=max(keep[m-1][n], prices[m]+keep[m-1][n-weight[m]]);``
maximum value of m equal to objects

Code: Select all

``for(int m=0; m<=objects; ++m) // For every item``
Maximum value of objects is 1000

Code: Select all

``````      cin >> objects;

for(int j=1; j<=objects; ++j)
{
cin >> prices[j] >> weight[j];
}
``````
Each test case begins with a line containing a single integer number N that indicates the number of objects (1 <= N <= 1000). Then follows N lines, each containing two integers: P and W. The first integer (1<=P<=100) corresponds to the price of object. The second integer (1<=W<=30) corresponds to the weight of object.

### Re: 10130 - SuperSales

Posted: Sat Jul 12, 2014 10:59 pm
Thanks a lot But now it gives me WA.

### Re: 10130 - SuperSales

Posted: Sun Jul 13, 2014 2:59 pm
First you must check your program for the input/output test posted in this thread.
tan_Yui wrote:My program outputs correct answer to the sample input,
but I got "wrong answer"....

I want to know the sample I/O for debugging.
Could someone help me?

Input :
• 4
2
77 7
66 6
2
5
5
6
32 16
43 12
26 4
50 8
20 3
27 9
4
25
23
21
19
5
1 1
2 1
3 1
2 2
5 5
10
1
2
3
4
5
6
7
8
9
10
10
1 1
4 3
4 3
4 4
5 4
8 6
10 7
9 7
11 8
13 9
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
(My) Output :
• 0
467
82
617
Thank you.
Mohammad Mahmudur Rahman wrote:My AC program gives -

Code: Select all

``````0
435
83
646
``````
Hope it helps.
Your program gives wrong output for last case:

Code: Select all

``````0
435
83
604
``````
Parameter n must go until 30 not 29.

Code: Select all

``         for(int n=0; n< 30; ++n) // For every weight``
It must be

Code: Select all

``         for(int n=0; n<= 30; ++n) // For every weight``
Each test case begins with a line containing a single integer number N that indicates the number of objects (1 <= N <= 1000). Then follows N lines, each containing two integers: P and W. The first integer (1<=P<=100) corresponds to the price of object. The second integer (1<=W<=30) corresponds to the weight of object. 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).
Your program is faster than mine because you avoided memseting array at each test case.

### Re: 10130 - SuperSales

Posted: Sun Jul 13, 2014 4:24 pm
Thank you so much . Its amazing how one small mistake can be so frustrating.

Thank you again

### Re: 10130 - SuperSale

Posted: Tue Jan 06, 2015 11:54 pm

### Re: 10130 - SuperSale

Posted: Wed Jan 07, 2015 12:10 am
You can solve each test case in O(N * MW + G)

### Re: 10130 - SuperSale

Posted: Sun Jan 25, 2015 10:54 pm
why tle??
see the optimization in "coin change and rock climbing" portion of shafayet's blog

### Re: 10130 - SuperSale

Posted: Mon May 18, 2015 11:49 pm
Getting WA but output are getting right

Code: Select all

``````#include<stdio.h>
int maxof(int ,int);
int main()
{
int i,j,m,n,x,y,objects_num,test_case;
int t[1010][31];
scanf("%d",&test_case);

while(test_case--)
{
int values[1010];
int weights[1010];
values[0]=0;
weights[0]=0;
scanf("%d",&objects_num);
for(m=1;m<=objects_num;m++)
{
scanf("%d %d",&values[m],&weights[m]);

}
for(x=0;x<=objects_num;x++)
{
t[x][0]=0;
}
for(y=0;y<=30;y++)
{
t[0][y]=0;
}
for(i=0;i<=objects_num;i++)
{
for(j=0;j<=30;j++)
{
if(j>=weights[i])
{
t[i][j]=maxof(t[i-1][j],t[i-1][j-weights[i]]+values[i]);

}
else
t[i][j]=t[i-1][j];

}
}
int max_sum=0;
int num_people=0;
int max_weight=0;
scanf("%d",&num_people);
while(num_people--)
{
scanf("%d",&max_weight);
max_sum=max_sum+t[objects_num][max_weight];
}
printf("%d",max_sum);
printf("\n");

}
return 0;
}
int maxof(int a,int b)
{
if (a>b)
return a;
else
return b;
}``````