PPTEST - Editorial

editorial
, , ,
1

PROBLEM LINKS:

Practice
Contest

Author: Vitaliy Herasymiv
Tester: Tasnim Imran Sunny
Editorialist: Tuan Anh

DIFFICULTY:

Easy

PREREQUISITES:

Dynamic Programming

PROBLEM:

There are N questions. The ith question needs T[i] minutes to learn and will give you C[i] × P[i] points in the tests. You have W minutes to learn the questions. Your job is to find which questions to learn to maximise your score.

EXPLANATION:

We need to choose a sub-set of N questions so that the total learning time does not exceed W and the total socore is
as large as possible. With the constraint N ≤ 100 we cannot try out all possible sub-sets since the number of
sub-sets can be 2 100 which is extremely large.

We need to use dynamic programming in this problem. Let F[i][j] be the maximal score you can get if you spend no more than j
minutes to learn some questions amongst the first i questions. Now, there are two cases:

  • If you choose to learn the ith question then you get maximally F[i - 1][j - T[i]] + C[i] × P[i] points. Be careful with the case where j < T[i].
  • If you do not learn the ith question then you get maximally F[i-1][j] points.
The complexity of this solution is O(N×W). For the initialization you need to set F[0][j] = 0 for all 0 ≤ j ≤ W.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

In the solution of problem setter and the tester an optimization is used to reduce the memory complexity.
With a little modification of the algorithm above we can solve this problem using a one-dimensional array of W elements.
The pseudo code is given below:

	FOR i -> 0 to W
		G[i] = 0
	ENDFOR
	
	(*)FOR i -> 1 to N
		FOR j -> W downto 0
			G[j] = max(G[j + T[i]], G[j] + C[i] × P[i])
	ENDFOR

After the ithiteration of the for loop (*), the value in G array is exactly as in the ith
row of the F array in the original algorithm. Notice that in the second For loop we need to consider the value of j in the decreasing order
so that each time we use G[j] to update G[j + T[i]] we know that the value in G[j] is the optimized value of using j minutes and the first (i - 1) questions only.

4 Likes
2

nice one.
very good for a naive programmer.

3

Can anyone tell me where I’m wrong in this approach

int a[101]={-1};

int DP(int i, int C[],int P[],int T[],int w){

if(a[i]>0)return a[i];
else{
if(i<0 || t==0) return 0;
else{
	if(t-T[i]>=0){
		a[i] = MAX(C[i]*P[i] + DP(i-1,C,P,T,w-T[i]),DP(i-1,C,P,T,w));
		//printf("%d\n",x);
		return a[i];
	}else{
		a[i] = DP(i-1,C,P,T,w);
		//printf("%d\n",x);
		return a[i];
	}
}

}
}

and answer=DP(n-1,C,P,T,w);

This approach is giving correct ans for sample case.
Thanks in advance.

4

Recursion involves two variable parameters, one is w and another one is i. So instead of using 1D array, just store it in a 2D array, say ans[i][w].

5

Can anybody tell, what’s wrong with my approach?

6

#include <stdio.h>
int main(){

int T,i,j;

scanf("%d",&T);
while(T--){

int n=0,w=0,x=0;

int temp=0,temp2=0;
scanf("%d %d",&n,&w);

    int c[n+1],p[n+1],arr[n+1],t2[n+1];

    for(i=0;i<n;i++)
    { scanf("%d",&c[i]);
      scanf("%d",&p[i]);
      scanf("%d",&x);
      t2[i]=w-x;
      arr[i]=c[i]*p[i]+t2[i];}

      for(i=0;i<n;i++)
      {
          for(j=0;j<n-1-i;j++)
          {
              if(arr[j]<arr[j+1])
              {
                  temp=arr[j];
                  arr[j]=arr[j+1];
                  arr[j+1]=temp;
                  temp2=t2[j];
                  t2[j]=t2[j+1];
                  t2[j+1]=temp2;
              }
              else if(arr[j]==arr[j+1])
              {
                  if((c[j]*p[j])<(c[j+1]*p[j+1])){
                    temp=arr[j]; temp2=t2[j];
                  arr[j]=arr[j+1];t2[j]=t2[j+1];
                  arr[j+1]=temp;t2[j+1]=temp2;
                  }
              }
          }
      }
   long long int sum=0,t_sum=0;
      for(i=0;i<n;i++)
      {  if(t_sum>t2[i]){continue;}
      else{
          sum+=arr[i]-t2[i];
        t_sum+=(w-t2[i]);
      }}
      printf("%lld\n",sum);}}

//Whats wrong in my answer