Maximum sum of values of N items in 0-1 Knapsack by reducing weight of at most K items in half

0 0 14 minutes read

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 maximum

Input: 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  value
 
int 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 approach
import 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  value
 
 
def 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 Code
 
value = [17, 20, 10, 15]
weight = [4, 2, 7, 5]
K = 1
W = 4
val_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 approach
using 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 code
var 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

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, Tuple
 
def 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

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!