10130 - SuperSale

[Safio]

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]

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]

For hover1178

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

[brianfry713]

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

[AbdAllah Boda]

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]

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]

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]

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.

[mratan16]

Thanks a lot But now it gives me WA.

[lighted]

First you must check your program for the input/output test posted in this thread.

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.

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.

[mratan16]

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

Thank you again

[uradura]

http://ideone.com/egHyyE
why tle??

[brianfry713]

You can solve each test case in O(N * MW + G)

[re_60]

http://ideone.com/egHyyE
why tle??

see the optimization in "coin change and rock climbing" portion of shafayet's blog

[progammingparina]

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