WikiGalaxy
0/1 Knapsack Problem
Introduction
The 0/1 Knapsack Problem is a classic problem in combinatorial optimization. It involves a knapsack with a weight limit and a set of items, each with a weight and value. The goal is to determine the maximum value that can be obtained by selecting items without exceeding the weight limit.
Problem Statement
Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
Approach
The problem can be solved using dynamic programming. We create a matrix where the rows represent items and the columns represent weight capacities. Each cell contains the maximum value achievable with the given capacity and available items.
public class Knapsack {
static int knapSack(int W, int wt[], int val[], int n) {
int K[][] = new int[n + 1][W + 1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = Math.max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
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));
}
}
Example 1: Basic Scenario
In this example, we have three items with weights 10, 20, and 30, and values 60, 100, and 120 respectively. The knapsack capacity is 50. The maximum value obtainable is 220 by taking items with weights 20 and 30.
Console Output:
220
0/1 Knapsack Problem with Fractional Values
Introduction
While the 0/1 Knapsack Problem does not allow splitting items, it is interesting to see how fractional values might affect the solution. This example considers integer weights with fractional values for demonstration.
Problem Statement
Consider the same set of items as before but with fractional values. The goal remains to maximize the total value without exceeding the weight limit.
Approach
The approach remains the same as the standard 0/1 Knapsack Problem, but the values are adjusted to demonstrate the effect of fractional values.
public class FractionalKnapsack {
static double knapSack(int W, int wt[], double val[], int n) {
double K[][] = new double[n + 1][W + 1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = Math.max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
public static void main(String args[]) {
double val[] = new double[] { 60.5, 100.75, 120.25 };
int wt[] = new int[] { 10, 20, 30 };
int W = 50;
int n = val.length;
System.out.println(knapSack(W, wt, val, n));
}
}
Example 2: Fractional Values
Here, the values are fractional: 60.5, 100.75, and 120.25. The maximum value obtainable remains similar due to the integer weight constraint, showcasing the problem's nature.
Console Output:
220.75
0/1 Knapsack Problem with Large Capacity
Introduction
This example explores how the 0/1 Knapsack Problem behaves when the knapsack capacity is significantly larger than the total weight of all items.
Problem Statement
With a large capacity, the challenge is to determine if all items can be included to maximize the total value.
Approach
The dynamic programming approach remains unchanged. The matrix will show that all items can be included when the capacity is larger than the total weight.
public class LargeCapacityKnapsack {
static int knapSack(int W, int wt[], int val[], int n) {
int K[][] = new int[n + 1][W + 1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = Math.max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
public static void main(String args[]) {
int val[] = new int[] { 60, 100, 120 };
int wt[] = new int[] { 10, 20, 30 };
int W = 100;
int n = val.length;
System.out.println(knapSack(W, wt, val, n));
}
}
Example 3: Large Capacity
With a knapsack capacity of 100, all items can be included, resulting in a total value of 280. This illustrates the scenario where capacity is not a limiting factor.
Console Output:
280
0/1 Knapsack Problem with Zero Capacity
Introduction
This example demonstrates the scenario where the knapsack has zero capacity, meaning no items can be included.
Problem Statement
With zero capacity, the maximum value that can be obtained is zero, as no items can be added to the knapsack.
Approach
The dynamic programming approach quickly reveals that with zero capacity, the only feasible solution is an empty knapsack.
public class ZeroCapacityKnapsack {
static int knapSack(int W, int wt[], int val[], int n) {
int K[][] = new int[n + 1][W + 1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = Math.max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
public static void main(String args[]) {
int val[] = new int[] { 60, 100, 120 };
int wt[] = new int[] { 10, 20, 30 };
int W = 0;
int n = val.length;
System.out.println(knapSack(W, wt, val, n));
}
}
Example 4: Zero Capacity
With zero capacity, the maximum value is 0. This scenario highlights the fundamental constraint of the knapsack problem.
Console Output:
0
0/1 Knapsack Problem with Equal Weights
Introduction
This example examines a situation where all items have the same weight but different values, testing the decision-making process based on value alone.
Problem Statement
With equal weights, the decision focuses on maximizing value, choosing the highest value items until the capacity is reached.
Approach
The dynamic programming solution will prioritize items with higher values when weights are equal, demonstrating value-based selection.
public class EqualWeightKnapsack {
static int knapSack(int W, int wt[], int val[], int n) {
int K[][] = new int[n + 1][W + 1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = Math.max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
public static void main(String args[]) {
int val[] = new int[] { 20, 50, 30 };
int wt[] = new int[] { 10, 10, 10 };
int W = 20;
int n = val.length;
System.out.println(knapSack(W, wt, val, n));
}
}
Example 5: Equal Weights
With all items weighing 10, the optimal solution is to choose the two items with the highest values, resulting in a total value of 80.
Console Output:
80
