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));
}
}
Comments