Bounded Knapsack (1/0) Solution in Java using Dynamic Programming
There are few items with weights and values, we need to find the items that contribute the maximum value that can be stored in knapsack of a particular capacity.
There are only 2 choices for each item, i.e. it can either be included or excluded from the bag.
Space complexity O(i*(capacity+1))
Time complexity O(i*(capacity+1))
package algos;
import java.math.MathContext;
import java.util.ArrayList;
class item {
public int weight;
public int value;
public item(int weight, int value) {
this.weight = weight;
this.value = value;
}
}
public class knapsackB {
public static void main(String[] args) {
item[] items = {
new item(1, 1),
new item(3, 4),
new item(4, 5),
new item(5, 7)
};
int bag = 7;
int[][] result = new int[items.length][bag + 1];
for (int it = 0; it < items.length; it++) {
for (int i = 0; i <= bag; i++) {
if (items[it].weight <= i) {
if (it != 0)
result[it][i] = Math.max(result[it - 1][i], items[it].value + result[it - 1][i - items[it].weight]);
else result[it][i] = items[it].value;
} else {
// use previous
if (it != 0)
result[it][i] = result[it - 1][i];
else result[it][i] = 0;
}
}
}
// Printing Result matrix
for (int it = 0; it < items.length; it++) {
for (int i = 0; i <= bag; i++) {
System.out.print(result[it][i] + " ");
}
System.out.println("");
}
int itemIndex = items.length - 1;
int weightIndex = bag;
// Printing the answer
System.out.println(result[itemIndex][weightIndex]);
ArrayList < item > finalBag = new ArrayList < item > ();
while (weightIndex != 0) {
if (result[itemIndex][weightIndex] != result[itemIndex - 1][weightIndex]) {
// include this
finalBag.add(items[itemIndex]);
weightIndex = weightIndex - items[itemIndex].weight;
itemIndex--;
} else {
itemIndex--;
}
}
// Printing the bag
for (item i: finalBag) {
System.out.println(i.value);
}
}
}
Output
0 1 1 1 1 1 1 1 0 1 1 4 5 5 5 5 0 1 1 4 5 6 6 9 0 1 1 4 5 7 8 9 9 5 4
Using Recursion
This is very inefficient.
/* A Naive recursive implementation of 0-1 Knapsack problem */
class Knapsack
{
// A utility function that returns maximum of two integers
static int max(int a, int b) { return (a > b)? a : b; }
// Returns the maximum value that can be put in a knapsack of capacity W
static int knapSack(int W, int wt[], int val[], int n)
{
// Base Case
if (n == 0 || W == 0)
return 0;
// If weight of the nth item is more than Knapsack capacity W, then
// this item cannot be included in the optimal solution
if (wt[n-1] > W)
return knapSack(W, wt, val, n-1);
// Return the maximum of two cases:
// (1) nth item included
// (2) not included
else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
knapSack(W, wt, val, n-1)
);
}
public static void main(String args[])
{
int val[] = new int[]{60, 100, 120};
int wt[] = new int[]{10, 20, 30};
int W = 50;
int n = val.length;
System.out.println(knapSack(W, wt, val, n));
}
}Output
220
Time Complexity = O(2^n).
The recursion tree is for following sample inputs.
wt[] = {1, 1, 1}, W = 2, val[] = {10, 20, 30}
K(3, 2) ---------> K(n, W)
/ \
/ \
K(2,2) K(2,1)
/ \ / \
/ \ / \
K(1,2) K(1,1) K(1,1) K(1,0)
/ \ / \ / \
/ \ / \ / \
K(0,2) K(0,1) K(0,1) K(0,0) K(0,1) K(0,0)Bounded Knapsack with Fractions allowed
In the above problem if we are allowed to include fractions, then we sort the items based on their value to weight ratios in descending order and include them in the knapsack, until it is full.
package algos;
import java.util.ArrayList;
import java.util.PriorityQueue;
class item {
public int weight;
public int value;
public item(int weight, int value) {
this.weight = weight;
this.value = value;
}
public class knapsackF {
public static void main(String[] args) {
PriorityQueue < item > queue =
new PriorityQueue < item > (4, (a, b) - > -Double.compare(a.value / (double) a.weight, b.value / (double) b.weight));
queue.add(new item(1, 1));
queue.add(new item(3, 4));
queue.add(new item(4, 5));
queue.add(new item(5, 7));
ArrayList < item > bag = new ArrayList < item > ();
int capacity = 7;
double val = 0;
item current;
while (!queue.isEmpty() && capacity != 0) {
current = queue.poll();
bag.add(current);
if (current.weight <= capacity) {
val += current.value;
capacity -= current.weight;
} else {
val += ((capacity / (double) current.weight) * current.value);
capacity = 0;
}
}
System.out.println(val);
for (item i: bag) {
System.out.println(i.value);
}
}
}
Output
9.666666666666666 7 4
Unbounded Knapsack solution
In this approach we use Dynamic programming to store the capacities incrementally to get the required maximum value at capacity.
Time complexity = O(i*(c+1))
Space complexity = O(c+1)
package algos;
class item {
public int weight;
public int value;
public item(int weight, int value) {
this.weight = weight;
this.value = value;
}
public class knapsackU {
public static void main(String[] args) {
item[] items = {
new item(1, 1),
new item(3, 4),
new item(4, 5),
new item(5, 7)
};
int capacity = 7;
int[] capacityList = new int[capacity + 1];
for (int cap = 0; cap <= capacity; cap++) {
for (item i: items) {
if (i.weight <= cap) {
capacityList[cap] = Math.max(capacityList[cap], i.value + capacityList[cap - i.weight]);
}
}
}
System.out.println(capacityList[capacity]);
}
}
Output
9
Unbounded Knapsack with Fractions allowed
This is a straightforward implementation, as we need to find the maximum ratio among the given items (value/weight) and then multiply it with the capacity of the bag.
Time complexity = O(i)
Space complexity = O(1)
package algos;
import java.math.MathContext;
class item {
public int weight;
public int value;
public item(int weight, int value) {
this.weight = weight;
this.value = value;
}
public class knapsackUF {
public static void main(String[] args) {
item[] items = {new item(1,1), new item(3,4), new item(4,5), new item(5,7)};
int capacity = 7;
double maxRatio = 0;
for(item i: items) {
maxRatio = Math.max(maxRatio, i.value/(double) i.weight);
}
System.out.println(maxRatio*capacity);
}
}
Output
9.799999999999999