Maximum sum of values of N items in 0-1 Knapsack by reducing weight of at most K items in half
Given weights and values of N items and the capacity W of the knapsack. Also given that the weight of at most K items can be changed to half of its original weight. The task is to find the maximum sum of values of N items that can be obtained such that the sum of weights of items in knapsack does not exceed the given capacity W.
Examples:
Input: W = 4, K = 1, value = [17, 20, 10, 15], weight = [4, 2, 7, 5]Output: 37
Explanation: Change the weight of at most K items to half of the weight in a optimal way to get maximum value. Decrease the weight of first item to half and add second item weight the resultant sum of value is 37 which is maximumInput: W = 8, K = 2, value = [17, 20, 10, 15], weight = [4, 2, 7, 5]
Output: 52
Explanation: Change the weight of the last item and first item and the add the weight the of the 2nd item, The total sum value of item will be 52.
Approach: Given problem is the variation of the 0 1 knapsack problem. Flag indicates number of items whose weight has been reduced to half. At every recursive call maximum of following cases is calculated and returned:
- Base case: If the index exceeds the length of values then return zero
- If flag is equal to K, maximum of 2 cases is considered:
- Include item with full weight if item’s weight does not exceed remaining weight
- Skip the item
- If flag is less than K, maximum of 3 cases is considered:
- Include item with full weight if item’s weight does not exceed remaining weight
- Include item with half weight if item’s half weight does not exceed remaining weight
- Skip the item
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum valueint maximum(int value[], int weight[], int weight1, int flag, int K, int index, int val_len){ // base condition if (index >= val_len) { return 0; } // K elements already reduced // to half of their weight if (flag == K) { // Dont include item int skip = maximum(value, weight, weight1, flag, K, index + 1, val_len); int full = 0; // If weight of the item is // less than or equal to the // remaining weight then include // the item if (weight[index] <= weight1) { full = value[index] + maximum(value, weight, weight1 - weight[index], flag, K, index + 1, val_len); } // Return the maximum of // both cases return max(full, skip); } // If the weight reduction to half // is possible else { // Skip the item int skip = maximum(value, weight, weight1, flag, K, index + 1, val_len); int full = 0; int half = 0; // Include item with full weight // if weight of the item is less // than the remaining weight if (weight[index] <= weight1) { full = value[index] + maximum(value, weight, weight1 - weight[index], flag, K, index + 1, val_len); } // Include item with half weight // if half weight of the item is // less than the remaining weight if (weight[index] / 2 <= weight1) { half = value[index] + maximum(value, weight, weight1 - weight[index] / 2, flag + 1, K, index + 1, val_len); } // Return the maximum of all 3 cases return max(full, max(skip, half)); }}int main(){ int value[] = { 17, 20, 10, 15 }; int weight[] = { 4, 2, 7, 5 }; int K = 1; int W = 4; int val_len = sizeof(value) / sizeof(value[0]); cout << (maximum(value, weight, W, 0, K, 0, val_len)); return 0;}// This code is contributed by Potta Lokesh |
Java
// Java implementation for the above approachimport java.io.*;import java.util.*;class GFG { // Function to find the maximum value static int maximum(int value[], int weight[], int weight1, int flag, int K, int index) { // base condition if (index >= value.length) { return 0; } // K elements already reduced // to half of their weight if (flag == K) { // Dont include item int skip = maximum(value, weight, weight1, flag, K, index + 1); int full = 0; // If weight of the item is // less than or equal to the // remaining weight then include // the item if (weight[index] <= weight1) { full = value[index] + maximum(value, weight, weight1 - weight[index], flag, K, index + 1); } // Return the maximum of // both cases return Math.max(full, skip); } // If the weight reduction to half // is possible else { // Skip the item int skip = maximum(value, weight, weight1, flag, K, index + 1); int full = 0; int half = 0; // Include item with full weight // if weight of the item is less // than the remaining weight if (weight[index] <= weight1) { full = value[index] + maximum(value, weight, weight1 - weight[index], flag, K, index + 1); } // Include item with half weight // if half weight of the item is // less than the remaining weight if (weight[index] / 2 <= weight1) { half = value[index] + maximum(value, weight, weight1 - weight[index] / 2, flag, K, index + 1); } // Return the maximum of all 3 cases return Math.max(full, Math.max(skip, half)); } } public static void main(String[] args) throws Exception { int value[] = { 17, 20, 10, 15 }; int weight[] = { 4, 2, 7, 5 }; int K = 1; int W = 4; System.out.println( maximum(value, weight, W, 0, K, 0)); }} |
Python3
# Python program for the above approach# Function to find the maximum valuedef maximum(value, weight, weight1, flag, K, index, val_len): # base condition if (index >= val_len): return 0 # K elements already reduced # to half of their weight if (flag == K): # Dont include item skip = maximum(value, weight, weight1, flag, K, index + 1, val_len) full = 0 # If weight of the item is # less than or equal to the # remaining weight then include # the item if (weight[index] <= weight1): full = value[index] + maximum( value, weight, weight1 - weight[index], flag, K, index + 1, val_len) # Return the maximum of # both cases return max(full, skip) # If the weight reduction to half # is possible else: # Skip the item skip = maximum( value, weight, weight1, flag, K, index + 1, val_len) full = 0 half = 0 # Include item with full weight # if weight of the item is less # than the remaining weight if (weight[index] <= weight1): full = value[index] + maximum( value, weight, weight1 - weight[index], flag, K, index + 1, val_len) # Include item with half weight # if half weight of the item is # less than the remaining weight if (weight[index] / 2 <= weight1): half = value[index] + maximum( value, weight, weight1 - weight[index] / 2, flag, K, index + 1, val_len) # Return the maximum of all 3 cases return max(full, max(skip, half))# Driver Codevalue = [17, 20, 10, 15]weight = [4, 2, 7, 5]K = 1W = 4val_len = len(value)print(maximum(value, weight, W, 0, K, 0, val_len))# This code is contributed by sanjoy_62. |
C#
// C# implementation for the above approachusing System;public class GFG { // Function to find the maximum value static int maximum(int[] value, int[] weight, int weight1, int flag, int K, int index) { // base condition if (index >= value.Length) { return 0; } // K elements already reduced // to half of their weight if (flag == K) { // Dont include item int skip = maximum(value, weight, weight1, flag, K, index + 1); int full = 0; // If weight of the item is // less than or equal to the // remaining weight then include // the item if (weight[index] <= weight1) { full = value[index] + maximum(value, weight, weight1 - weight[index], flag, K, index + 1); } // Return the maximum of // both cases return Math.Max(full, skip); } // If the weight reduction to half // is possible else { // Skip the item int skip = maximum(value, weight, weight1, flag, K, index + 1); int full = 0; int half = 0; // Include item with full weight // if weight of the item is less // than the remaining weight if (weight[index] <= weight1) { full = value[index] + maximum(value, weight, weight1 - weight[index], flag, K, index + 1); } // Include item with half weight // if half weight of the item is // less than the remaining weight if (weight[index] / 2 <= weight1) { half = value[index] + maximum(value, weight, weight1 - weight[index] / 2, flag, K, index + 1); } // Return the maximum of all 3 cases return Math.Max(full, Math.Max(skip, half)); } } // Driver code public static void Main(String[] args) { int[] value = { 17, 20, 10, 15 }; int[] weight = { 4, 2, 7, 5 }; int K = 1; int W = 4; Console.WriteLine( maximum(value, weight, W, 0, K, 0)); }}// This code is contributed by shikhasingrajput |
Javascript
<script>// javascript implementation for the above approach // Function to find the maximum value function maximum(value, weight , weight1, flag , K , index) { // base condition if (index >= value.length) { return 0; } // K elements already reduced // to half of their weight if (flag == K) { // Dont include item var skip = maximum(value, weight, weight1, flag, K, index + 1); var full = 0; // If weight of the item is // less than or equal to the // remaining weight then include // the item if (weight[index] <= weight1) { full = value[index] + maximum( value, weight, weight1 - weight[index], flag, K, index + 1); } // Return the maximum of // both cases return Math.max(full, skip); } // If the weight reduction to half // is possible else { // Skip the item var skip = maximum( value, weight, weight1, flag, K, index + 1); var full = 0; var half = 0; // Include item with full weight // if weight of the item is less // than the remaining weight if (weight[index] <= weight1) { full = value[index] + maximum( value, weight, weight1 - weight[index], flag, K, index + 1); } // Include item with half weight // if half weight of the item is // less than the remaining weight if (weight[index] / 2 <= weight1) { half = value[index] + maximum( value, weight, weight1 - weight[index] / 2, flag, K, index + 1); } // Return the maximum of all 3 cases return Math.max(full, Math.max(skip, half)); } }// Driver codevar value = [ 17, 20, 10, 15 ];var weight = [ 4, 2, 7, 5 ];var K = 1;var W = 4;document.write( maximum(value, weight, W, 0, K, 0));// This code is contributed by Princi Singh </script> |
Output
37
Time Complexity: O(3^N)
Auxiliary Space: O(N)
Given problem is the variation of the 0-1 knapsack problem. In traditional 0-1 Knapsack problem, we only have to choices: skip the i-th item or take it.
However, in this case we will have 3 choices as mentioned in the recursive approach.
Efficient Approach (Dynamic Programming):
In Dynamic programming, we will work considering the same cases as above. We shall consider a 3D DP table where the state DP[i][j][k] will denote the maximum value we can obtain if we are considering values from 1 to i-th, weight of the knapsack is j and we can half the weight of at most k values. Basically, we are adding one extra state, the number of weights that can be halved in a traditional 2-D 01 knapsack DP matrix.
Now, three possibilities can take place:
- Include item with full weight if the item’s weight does not exceed the remaining weight
- Include the item with half weight if the item’s half weight does not exceed the remaining weight
- Skip the item
Now we have to take the maximum of these three possibilities. If we do not take the i-th weight then dp[i][j][k] would remain equal to dp[i – 1][j][k], just llike traditional knapsack. If we include item with half weight then dp[i][j][k] would be equal to dp[i – 1][j – wt[i] / 2][k – 1] + val[i] as after including i-th value our remaining knapsack capacity would be j – wt[i] / 2 and our number of half operations would increase by 1. Similarly, if we include item with full weight then dp[i][j][k] would be equal to dp[i – 1][j – wt[i]][k] + val[i] as knapsack capacity in this case would reduce to j – wt[i].
We simply take the maximum of all three choices.
Below is the code implementation of above approach:
C++
#include <iostream>#include <vector>#include <cstring>using namespace std;int getMaximumNutrition(int W, vector<int> value, vector<int> weight, int x) { int n=value.size(); int dp[n + 1][W + 1][x + 1]; /* dp[i][j][k] denotes the maximum value that we can obtain if we are considering first i elements of array, our capacity is j and we can use only k half operations */ memset(dp, 0, sizeof(dp)); for(int i = 1;i <= n; i++) { for(int j = 1;j <= W; j++) { int lim = x; if(lim > i) { lim = i; } for(int k = 0;k <= lim; k++) { dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j][k]);//skip int val = j - (weight[i - 1] / 2); if(val >= 0 && k > 0)//ensure that j-weight[i-1]/2 and k-1 don't become -ve { dp[i][j][k] = max(dp[i - 1][val][k - 1]+value[i - 1], dp[i][j][k]); //take item applying half operation } val = j - weight[i - 1]; if(val >= 0)//ensure that j-weight[i-1] doesn't become -ve { dp[i][j][k] = max(dp[i - 1][val][k] + value[i - 1], dp[i][j][k]); //take item without applying half operation } } } } return dp[n][W][x];}int main() { vector<int> value = {17, 20, 10, 15}; vector<int> weight = {4, 2, 7, 5}; int x = 1; int W = 4; cout << getMaximumNutrition(W, value, weight, x); return 0;} |
Java
import java.util.*;public class Main { static int getMaximumNutrition(int W, int[] value, int[] weight, int x) { int n = value.length; int[][][] dp = new int[n + 1][W + 1][x + 1]; /* dp[i][j][k] denotes the maximum value that we can obtain if we are considering first i elements of array, our capacity is j and we can use only k half operations */ for (int i = 1; i <= n; i++) { for (int j = 1; j <= W; j++) { int lim = x; if (lim > i) { lim = i; } for (int k = 0; k <= lim; k++) { dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i][j][k]); // skip int val = j - (weight[i - 1] / 2); if (val >= 0 && k > 0) // ensure that // j-weight[i-1]/2 and k-1 // don't become -ve { dp[i][j][k] = Math.max(dp[i - 1][val][k - 1] + value[i - 1], dp[i][j][k]); // take item applying half operation } val = j - weight[i - 1]; if (val >= 0) // ensure that j-weight[i-1] // doesn't become -ve { dp[i][j][k] = Math.max(dp[i - 1][val][k] + value[i - 1], dp[i][j][k]); // take item without applying half // operation } } } } return dp[n][W][x]; } public static void main(String[] args) { int[] value = { 17, 20, 10, 15 }; int[] weight = { 4, 2, 7, 5 }; int x = 1; int W = 4; System.out.println( getMaximumNutrition(W, value, weight, x)); }}// This code is contributed by garg28harsh. |
C#
using System;class GFG { static int getMaximumNutrition(int W, int[] value, int[] weight, int x) { int n = value.Length; int[, , ] dp = new int[n + 1, W + 1, x + 1]; /* dp[i][j][k] denotes the maximum value that we can obtain if we are considering first i elements of array, our capacity is j and we can use only k half operations */ for (int i = 1; i <= n; i++) { for (int j = 1; j <= W; j++) { int lim = x; if (lim > i) { lim = i; } for (int k = 0; k <= lim; k++) { dp[i, j, k] = Math.Max(dp[i - 1, j, k], dp[i, j, k]); // skip int val = j - (weight[i - 1] / 2); if (val >= 0 && k > 0) // ensure that // j-weight[i-1]/2 and k-1 // don't become -ve { dp[i, j, k] = Math.Max(dp[i - 1, val, k - 1] + value[i - 1], dp[i, j, k]); // take item applying half operation } val = j - weight[i - 1]; if (val >= 0) // ensure that j-weight[i-1] // doesn't become -ve { dp[i, j, k] = Math.Max(dp[i - 1, val, k] + value[i - 1], dp[i, j, k]); // take item without applying half // operation } } } } return dp[n, W, x]; } static void Main() { int[] val = { 17, 20, 10, 15 }; int[] weight = { 4, 2, 7, 5 }; int x = 1; int W = 4; Console.Write( getMaximumNutrition(W, val, weight, x)); }}// This code is contributed by garg28harsh. |
Javascript
function getMaximumNutrition(W, value, weight, x) { let n=value.length; /* dp[i][j][k] denotes the maximum value that we can obtain if we are considering first i elements of array, our capacity is j and we can use only k half operations */ let dp = new Array(n+1); for(let i = 0; i < n + 1; i++) { dp[i] = new Array(W+1); for(let j = 0; j < W + 1; j++) { dp[i][j] = new Array(x+1); for(let k = 0; k < x + 1; k++) { dp[i][j][k] = 0; } } } for(let i = 1;i <= n; i++) { for(let j = 1;j <= W; j++) { let lim = x; if(lim > i) { lim = i; } for(let k = 0;k <= lim; k++) { dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i][j][k]);//skip let val = j - Math.round(weight[i - 1] / 2); if(val >= 0 && k > 0)//ensure that j-weight[i-1]/2 and k-1 don't become -ve { dp[i][j][k] = Math.max(dp[i - 1][val][k - 1]+value[i - 1], dp[i][j][k]); //take item applying half operation } val = j - weight[i - 1]; if(val >= 0)//ensure that j-weight[i-1] doesn't become -ve { dp[i][j][k] = Math.max(dp[i - 1][val][k] + value[i - 1], dp[i][j][k]); //take item without applying half operation } } } } return dp[n][W][x];} let value = [17, 20, 10, 15]; let weight = [4, 2, 7, 5]; let x = 1; let W = 4; console.log(getMaximumNutrition(W, value, weight, x)); // This code is contributed by garg28harsh. |
Python3
# Python3 code for the above approach:from typing import List, Tupledef getMaximumNutrition(W: int, value: List[int], weight: List[int], x: int) -> int: n = len(value) dp = [[[0 for _ in range(x+1)] for _ in range(W+1)] for _ in range(n+1)] for i in range(1, n+1): for j in range(1, W+1): lim = min(x, i) for k in range(lim+1): dp[i][j][k] = max(dp[i-1][j][k], dp[i][j][k]) #skip val = j - (weight[i-1] // 2) if val >= 0 and k > 0: #ensure that j-weight[i-1]/2 and k-1 don't become negative dp[i][j][k] = max(dp[i-1][val][k-1] + value[i-1], dp[i][j][k]) # take item applying half operation val = j - weight[i-1] if val >= 0: #ensure that j-weight[i-1] doesn't become negative dp[i][j][k] = max(dp[i-1][val][k] + value[i-1], dp[i][j][k]) # take item without applying half operation return dp[n][W][x]if __name__ == "__main__": value = [17, 20, 10, 15] weight = [4, 2, 7, 5] x = 1 W = 4 print(getMaximumNutrition(W, value, weight, x)) |
Output
37
Time Complexity: O(n*W*K)
Auxiliary Space: O(n*W*K)
Note that space complexity can be further reduced to O(W*2*2) as for computing some dp[i][j][k] we only need to know values at current and previous i-th and k-th state. Time complexity will remain the same.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
