COW206 - Editorial

editorial
,
1

PROBLEM LINK:

Practice

Code - O - War
video solution

Author: arnie8991
Editorialist: arnie8991

DIFFICULTY:

MEDIUM

PREREQUISITES:

0-1 Knapsack

EXPLANATION:

This problem is just a slight modification of the classic 0-1 Knapsack problem that can be easily solved by using dynamic programming. We only need to take care of the poisoned apples which we can either remove from the list or assign a high cost and low nutritional value.

SOLUTIONS:

[details="Setter’s Solution]

// 1. remove poisoned apples
// 2. We can assign a very high cost and a very low nutrition to the poisoned apples


import java.util.*;

class Main{

    public static int knapSack(int W, int wt[], int val[], int n) 
    { 
        int i, w; 
        int K[][] = new int[n+1][W+1]; 
        
        for (i = 0; i <= n; i++) 
        { 
            for (w = 0; w <= W; w++) 
            { 
                if (i==0 || w==0) 
                    K[i][w] = 0; 
                else if (wt[i-1] <= w) 
                    K[i][w] = Math.max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]); 
                else
                    K[i][w] = K[i-1][w]; 
            } 
        } 
        
        return K[n][W]; 
    } 

    public static void main(String args[]){
        Scanner sc = new Scanner (System.in);

        int n = sc.nextInt();
        int b = sc.nextInt();
        int m = sc.nextInt();

        int cost_arr[] = new int[n];
        int nutrition_arr[] = new int[n];
        int poi_arr[] = new int[b];

        for(int  i = 0;i<n;++i){ cost_arr[i] = sc.nextInt(); }
        for(int  i = 0;i<n;++i){ nutrition_arr[i] = sc.nextInt(); }
        for(int  i = 0;i<b;++i){ poi_arr[i] = sc.nextInt(); }

        for(int i: poi_arr){
            cost_arr[i] = 9999999;
            nutrition_arr[i] = -9999999;
        }

        int result = knapSack(m, cost_arr, nutrition_arr, n);

        System.out.println(result);

    }

}

// Time complexity : O(NW)
// Space Complexity: O(NW)

[details=“Tester’s Solution”]

3 Likes
2 
#include<bits/stdc++.h>
#define ll long long
#define PI 3.14
#define all(x) x.begin(),x.end()
#define deb(x) cout<<#x<<" = "<<x<<endl
#define sortall1(x) sort(all(x))
#define pb push_back
#define tr(it,a) for(auto it=a.begin();it1!=a.end();it++)
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define mem(a,b) memset(a,(b),sizeof(a))
#define MOD 1000000007
#define fi first
#define se second
#define mp make_pair
using namespace std;
int dp[1002][1002];
ll solve(vector<ll>&cost,vector<ll>&value,ll size,vector<ll>&index,ll zero,ll sizeb,ll start,ll money)
{
    
    if(size==start)
    {
        return dp[start][money]=0;
    }
    // if bad apples just skip this 
    if(dp[start][money]!=-1)
    {
        return dp[start][money];
    }
    if(cost[start]>money)
    {
        return dp[start][money]=solve(cost,value,size,index,zero,sizeb,start+1,money);
    }
    else if(start==index[zero])
    {
        return dp[start][money]=solve(cost,value,size,index,zero+1,sizeb,start+1,money);
    }
    
    else
    {
        return dp[start][money]=max( solve(cost,value,size,index,zero,sizeb,start+1,money)  , value[start]+solve(cost,value,size,index,zero+1,sizeb,start+1,money-cost[start]) );
    }
}
int main() 
{ 
 for(int i=0;i<1002;i++)
 {
     for(int j=0;j<1002;j++)
     {
         dp[i][j]=-1;
     }
 }
     
 ll n,b,m;
 cin>>n>>b>>m;
 vector<ll>cost,value,index;
 for(ll i=0;i<n;i++)
 {
     ll x;
     cin>>x;
     cost.pb(x);
     }
     
 for(ll i=0;i<n;i++)
 {
     ll y;
     cin>>y;
     value.pb(y);
 }
 for(int i=0;i<b;i++)
 {
     ll y;
     cin>>y;
     index.pb(y);
 }
 sort(index.begin(),index.end());
 cout<<solve(cost,value,n,index,0,b,0,m);
       
       
   
    
	
	return 0; 
}

what is wrong in this apporach?