PPTEST - Editorial

[admin]

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 i^th 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 ¹⁰⁰ 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 i^th 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 i^th 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 i^thiteration of the for loop (*), the value in G array is exactly as in the i^th
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.

[hrily]

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.

[boovi]

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

[gagand33p]

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

Ideone.com

[ab_sanyal]

#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

[imrajeshpal]

nice one.
very good for a naive programmer.

[ankurshhhh123]

if anyone found any error in my code please reply

#include
#include
#define ll long long int
using namespace std;
struct polo{
ll prod;
ll time;
};
bool compare(polo a , polo b)
{
return a.prod<b.prod;
}
int main()
{
ll test;
cin>>test;
while(test–)
{
ll n,w,ans=0,netans=0;
cin>>n>>w;
ll c[n],p[n],t[n];
polo pr[n];
for(ll i=0;i<n;i++)
{
cin>>c[i]>>p[i]>>t[i];
pr[i].prod=c[i]*p[i];
pr[i].time=t[i];
}
sort(pr,pr+n,compare);
for(ll j=0;j<n-1;j++)
{
ll num=w,ans=0;
for(ll i=n-1-j;i>=0;i–)
{
if(pr[i].time<=num)
{
ans+=pr[i].prod;
num-=pr[i].time;
}
}
netans=max(netans,ans);
}
cout<<netans<<endl;
}
return 0;
}

[sandy5858]

this problem has an analogy with the standard 0/1 KNAPSACK problem

[simbaa]

greedy approch does not work for 0-1 knap sac problem
counter test case:
1
3 20
1 3 18
1 2 10
1 2 10

[vanshmotwani16]

hello coders community!! Since i m a beginner here can anyone of you experienced coder would help me to help/advice me to figure out whats wrong in my approach towards this question and also provide some testcases for same…
Its a request please guide me…
my solution link:- CodeChef: Practical coding for everyone

[shinigami_017]

/* AUTHOR - ANIMESH BARUN*/
/AKA - THE NOOB CODER/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;
typedef pair<string, string> pss;
typedef vector vi;
typedef vector vvi;
typedef vector vii;
typedef vector vl;
typedef vector vvl;

#define F first
#define S second
#define MP make_pair
#define PB push_back
#define INF INT_MAX
#define MOD 1000000007

void init_code()
{
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif // ONLINE_JUDGE
}

int lcm(int a,int b)
{
return a*b/__gcd(a,b);
}

bool isvowel(char ch)
{
return (ch == ‘a’) || (ch == ‘e’) ||(ch == ‘i’) ||(ch == ‘o’) ||(ch == ‘u’);
}

int f(int q,int w,int n,vector<vector> &a,vector<vector> &dp)
{
if(q==0)
{
if(w>=a[0][2])
{
return a[0][0]*a[0][1];
}
else
{
return 0;
}
}
int p = INT_MIN;
if(w>=a[q][2])
{
p = a[q][0]*a[q][1] + f(q-1,w-a[q][2],n,a,dp);
}
int np = f(q-1,w,n,a,dp);
return dp[q][w]=max(p,np);
}

int main()
{
init_code();
ios_base::sync_with_stdio(false);
cin.tie(NULL);
/-------------------------------------------CODE BELOW THIS--------------------------------------------/
int t;
cin>>t;
while(t–)
{
int n,w;
cin>>n>>w;
vector<vector> a(n,vector(3)),dp(n,vector(w+1,-1));
for(int i=0;i<n;i++)
{
for(int j=0;j<3;j++)
{
cin>>a[i][j];
}
}
cout<<f(n-1,w,n,a,dp);
}
/-------------------------------------------CODE ABOVE THIS--------------------------------------------/
return 0;
}

Please can anyone help me ?
What is wrong with my code. Its giving correct output for all test cases but when I submit the solutions, its giving me WA.