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

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

Re: 10130 - SuperSales

Post by Safio » 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;
	}
}

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

Re: 10130 - SuperSales

Post by hover1178 » 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;

}

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

Re: 10130 - SuperSales

Post by shuvokr » 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 .

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

Post by brianfry713 » 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
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

Post by AbdAllah Boda » 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

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

Re: super sale problem is WA

Post by lourencohen » 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

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

Re: 10130 - SuperSales

Post by mratan16 » 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; 
}

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

Re: 10130 - SuperSales

Post by lighted » 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.
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

Post by mratan16 » Sat Jul 12, 2014 10:59 pm

Thanks a lot :) But now it gives me WA.

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

Re: 10130 - SuperSales

Post by lighted » 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. :wink:
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

Post by mratan16 » Sun Jul 13, 2014 4:24 pm

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

Thank you again

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

Re: 10130 - SuperSale

Post by uradura » Tue Jan 06, 2015 11:54 pm


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

Re: 10130 - SuperSale

Post by brianfry713 » Wed Jan 07, 2015 12:10 am

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
Location: Bangladesh

Re: 10130 - SuperSale

Post by re_60 » Sun Jan 25, 2015 10:54 pm

uradura wrote:http://ideone.com/egHyyE
why tle??
see the optimization in "coin change and rock climbing" portion of shafayet's blog :D :lol:
keep calm and smile on

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

Re: 10130 - SuperSale

Post by progammingparina » 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;
    }
Last edited by brianfry713 on Fri Jun 19, 2015 6:55 am, edited 1 time in total.
Reason: Added code blocks

Post Reply

Return to “Volume 101 (10100-10199)”