Knapsack With Duplicate Items in Java
Given N elements in the set, each represented by the array weight and value, respectively, and each having a weight and a value, in addition to a knapsack that can only hold W pounds, our task is to pack the knapsack so that we can make the maximum amount of profit possible. Return the profit.
Note: We may take any number of duplicates of each item.
Example 1:
Input:
N = 2
W = 3
value = {1, 1}
weight = {2, 1}
Output:
The maximum profit is 3
Explanation:
Select the element the second three times. Profit total is 1 + 1 + 1 = 3. Moreover, the total weight is less than three, or 1 + 1 + 1 = 3.
Approach: Using Dynamic Programming
In general, using dynamic programming is the solution to the knapsack problem with duplicate items. To hold the maximum value that may be achieved for different weight capacities, we build a dynamic programming table. Iteratively, we update this table in search of the most optimal solution.
Algorithm:
Step 1: Create a 2D array called dp[][] to hold each of the subproblems' results.
Step 2: Call function solution to recursively compute the maximum profit.
Step 3: Return the whole amount of profit made.
Step 4: Base case: Return 0 if there are no further things to take into consideration.
Step 5: Return the result if it has already been precomputed for the current state.
Step 6: Delete the item if its weight exceeds the available space.
Step 7: Find the maximum profit by adding or subtracting the item that is currently being used.
Step 8: Update the dp array's outcome.
Step 9: Return the highest profit possible for the existing situation.
Implementation:
FileName:
import java.io.*;
import java.util.*;
public class KnapsackSolution
{
static int knapSack(int N, int W, int profit[], int weight[])
{
int dp[][] = new int[N+1][W+1];
for(int row[] : dp)
{
Arrays.fill(row,-1);
}
int maxProfit = solve(profit, weight, W, dp, N-1);
return maxProfit;
}
public static int solve(int profit[],int weight[],int W,int dp[][],int position)
{
if(position<0)
{
return 0;
}
if(dp[position][W]!=-1)
{
return dp[position][W];
}
if(weight[position] > W)
{
//exclude : if curr weight is grater than capacity.
return dp[position][W] = solve(profit, weight, W, dp, position - 1);
}
else
{
return dp[position][W] = Math.max(
solve(profit,weight, W - weight[position], dp, position) + profit[position],//include
solve(profit, weight, W, dp, position - 1)//exclude
);
}
}
public static void main(String[] args)
{
int N = 2; // Number of items
int W = 3; // capacity of Knapsack
int[] profit = {1, 1}; // Profits of the items
int[] weight = {2, 1}; // Weights of each items
int maxi_Profit = KnapsackSolution.knapSack(N, W, profit, weight);
System.out.println("The Maximum Profit of the knapsack: " + maxi_Profit);
}
}
Output:
The Maximum Profit of the knapsack: 3
Complexity Analysis:
The above method has an O(N * W) time complexity, where N is the number of items and W is the knapsack's maximum weight. With the dynamic programming table, the space complexity is O(W).