- Get link
- Other Apps

### Featured Post

Posted by
Varun
on

- Get link
- Other Apps

Imagine a hiker's backpack (the knapsack) with limited space (capacity).

They have a collection of items, each with a value (usefulness) and a weight (space it occupies).

The goal is to fill the backpack with the most valuable combination of items, without exceeding its weight capacity.

#### Visualizing the Items

#### The Knapsack

#### Decision-Making

- Can't fit all items directly (total weight 60).
- Optimal choice would be to put these items in the bag
- Item: {value: 120, weight: 30}
- Item: {value: 100, weight: 20}

#### Optimal Solution

```
KNAPSACK (capacity 50)
(value 120, weight 30)
```

#### Key Points

- Knapsack represents a resource constraint (limited capacity).
- Items represent choices with associated values and constraints (weight).
- Goal is to maximize value within the constraint.
- Often involves trade-offs and strategic decision-making.

In formal language, given a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity, find the subset of items that maximizes the total value while fitting within the weight capacity.

### Dynamic Programming Approach

Create a table

`dp`

:- Dimensions:
`(n + 1) x (W + 1)`

, where`n`

is the number of items and`W`

is the knapsack capacity. `dp[i][w]`

stores the maximum value achievable using items up to the`i-th`

item and with a maximum weight of`w`

.

- Dimensions:
Fill the table:

- Base cases:
`dp[0][w] = 0`

for all`w`

(no items, value is 0).`dp[i][0] = 0`

for all`i`

(zero weight capacity, value is 0).

- Recursive formula:
`dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]])`

if`weight[i] <= w`

(Choose between including or excluding the`i-th`

item)`dp[i][w] = dp[i-1][w]`

otherwise (Item cannot be included due to weight constraint)

- Base cases:
Solution:

- The maximum value is
`dp[n][W]`

(using all items with the knapsack capacity). - Backtrack to find the selected items.

```
import java.util.ArrayList;
import java.util.List;
public class Knapsack {
public static List
```- knapsack(List
- items, int capacity) {
int[][] dp = new int[items.size() + 1][capacity + 1];
// Build table dp[][] in a bottom-up manner
for (int i = 0; i <= items.size(); i++) {
for (int w = 0; w <= capacity; w++) {
if (i == 0 || w == 0) {
dp[i][w] = 0;
} else if (items.get(i - 1).weight <= w) {
dp[i][w] = Math.max(items.get(i - 1).value + dp[i - 1][w - items.get(i - 1).weight], dp[i - 1][w]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
// Reconstruct the solution
List
- selectedItems = new ArrayList<>();
int i = items.size(), w = capacity;
while (i > 0 && w > 0) {
if (dp[i][w] != dp[i - 1][w]) {
selectedItems.add(items.get(i - 1));
w -= items.get(i - 1).weight;
}
i--;
}
return selectedItems;
}
public static void main(String[] args) {
List
- items = new ArrayList<>();
items.add(new Item(60, 10));
items.add(new Item(100, 20));
items.add(new Item(120, 30));
int capacity = 50;
List
- selected = knapsack(items, capacity);
System.out.println("Selected items: " + selected);
}
public static class Item {
int value;
int weight;
Item(int value, int weight) {
this.value = value;
this.weight = weight;
}
@Override
public String toString() {
return "Item: {value: " + value + ", weight: " + weight + "}";
}
}
}

## Explanation of code

1. Item Class:

- Represents an item with its value and weight.

2. knapsack() Method:

- Takes a list of items and a knapsack capacity as input.
- Uses dynamic programming to solve the 0-1 Knapsack Problem.
- Returns a list of selected items that maximize the total value without exceeding the capacity.

#### Steps

- Create a 2D DP array: Stores intermediate results for subproblems.
- Fill the DP array:
- Iterate through items and capacities.
- For each cell, calculate the maximum value achievable considering the current item and remaining capacity.

- Reconstruct the solution: Backtrack through the DP array to find the selected items.

#### Take away points

- Bottom-up approach: Builds the solution from smaller subproblems to the final solution.
- Dynamic programming principle: Avoids redundant calculations by storing intermediate results.
- Time complexity: O(nW), where n is the number of items and W is the capacity.
- Space complexity: O(nW), due to the DP array.

- Get link
- Other Apps

## Comments

## Post a Comment

Please post your valuable suggestions