## 10130 - SuperSale

Moderator: Board moderators

Safio
New poster
Posts: 6
Joined: Tue Jan 22, 2013 5:03 pm

### Re: 10130 - SuperSales

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,W,F,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[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;
}
}``````

hover1178
New poster
Posts: 3
Joined: Mon Jan 21, 2013 11:57 am

### Re: 10130 - SuperSales

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,w;
int dp;// 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;

}``````

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm

### Re: 10130 - SuperSales

For hover1178
maximum item is 1 <= N <= 1000... Now see that int p,w;...Hope that its help you .

Code: Select all

``enjoying life ..... ``

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

### Re: 10130 - SuperSales

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
Check input and AC output for thousands of problems on uDebug!

AbdAllah Boda
New poster
Posts: 6
Joined: Sat Dec 01, 2012 2:52 pm

### Re: 10130 - SuperSales

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
``````

lourencohen
New poster
Posts: 1
Joined: Tue Mar 11, 2014 10:06 am

### Re: super sale problem is WA

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

mratan16
New poster
Posts: 21
Joined: Fri May 16, 2014 12:36 am

### Re: 10130 - SuperSales

Code: Select all

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

using namespace std;

int keep;

int prices;
int weight;

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;

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;
}
``````

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10130 - SuperSales

You must increase first paramater

Code: Select all

``int keep;``
It must be

Code: Select all

``int keep;``
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.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

mratan16
New poster
Posts: 21
Joined: Fri May 16, 2014 12:36 am

### Re: 10130 - SuperSales

Thanks a lot But now it gives me WA.

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10130 - SuperSales

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,

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. A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

mratan16
New poster
Posts: 21
Joined: Fri May 16, 2014 12:36 am

### Re: 10130 - SuperSales

Thank you so much . Its amazing how one small mistake can be so frustrating.

Thank you again

New poster
Posts: 11
Joined: Thu Jan 01, 2015 10:31 am

### Re: 10130 - SuperSale

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

### Re: 10130 - SuperSale

You can solve each test case in O(N * MW + G)
Check input and AC output for thousands of problems on uDebug!

re_60
New poster
Posts: 2
Joined: Sun Jan 25, 2015 10:44 pm

### Re: 10130 - SuperSale

why tle??
see the optimization in "coin change and rock climbing" portion of shafayet's blog  keep calm and smile on

progammingparina
New poster
Posts: 1
Joined: Mon May 18, 2015 11:45 pm

### Re: 10130 - SuperSale

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;
scanf("%d",&test_case);

while(test_case--)
{
int values;
int weights;
values=0;
weights=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;
}
for(y=0;y<=30;y++)
{
t[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;
}``````
Last edited by brianfry713 on Fri Jun 19, 2015 6:55 am, edited 1 time in total.