Search

The 0-1 Knapsack Problem

Updated: Apr 10, 2021

We are given an array of values values and an array of weights weights:

  • values[i] corresponds to the value of the i'th item

  • weights[i] corresponds to the weight of the i'th item

Given these two lists and an integer W, find a subset of the items in this "knapsack" that has maximal overall value, yet stays <= maxWeight in total weight.



Example 1:

Input:
values = [60, 50, 70, 30]
weights = [5, 3, 4, 2]
maxWeight = 8

Output: 120
Explanation: We take items 1 and 2 (zero-indexed) for a total value of 120 and a total weight of 7.

Example 2:

Input:
values = [60, 100, 120, 80, 30]
weights = [10, 20, 30, 40, 50]
maxWeight = 400

Output: 390
Explanation: We take all items for a total value of 390 and a total weight of 150, still below 400.

Constraints:

  • You can not split an item

  • Once you select an item you can not select it again

Solution:

public class Knapsack 
{
    public static void main(String args[]) 
    {
        int W = 5;
        int[] values = {40, 30, 20, 10};
        int[] weights = {3, 2, 1, 4};
        int[][] dp = new int[values.length + 1][W + 1]; 
        for (int i = 0; i <= values.length; i++) 
        { 
	    for (int j = 0; j <= W; j++) 
	    {    
		if (i == 0 || j == 0) dp[i][j] = 0; 
		else if (weights[i-1] > j)  dp[i][i] = dp[i - 1][j]; 
                else dp[i][j] = Math.max(values[i-1] + dp[i - 1][j - weights[i-1]], dp[i - 1][j]); 
            } 
        }
        System.out.println(dp[values.length][W]); 
        System.out.println(Arrays.deepToString(dp)); 
    }
}



18 views0 comments

Recent Posts

See All

A string s is called good if there are no two different characters in s that have the same frequency. Given a string s, return the minimum number of characters you need to delete to make s good. The f

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.