PPTEST - Editorial

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

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.

5 Likes

nice one.
very good for a naive programmer.

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

}
}

This approach is giving correct ans for sample case.

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].

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

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