# Knapsack (Unbounded) Pattern

These problems discussed below conform to one knapsack pattern called Unbounded Knapsack. Using solutions to the knapsack problem and a minor modification, you can solve almost all of the following problems. We'll discuss this as we explain the code and the approach to these problems.

**Problems Discussed**

- The Unbounded Knapsack Problem
- Rod cutting
- Coin Change II
- Coin Change I (Unbounded Knapsack Way)
- Maximum Ribbon Cut

## The Unbounded Knapsack Problem

To recap in the \(0/1\) knapsack case we either include and item or not. Each item has one instance in the universe. Either we take one of e$$ach item in the bag or not. **But** in the unbounded knapsack case we can take any number of same item as we wish. Once we make a decision that we don't or we would take some element, we don't go back and rethink about it.

Multiple occurences of same item is allowed. If at some time \(t\) we don't choose some element then we don't consider that element again (we call it processed). In \(0/1\) knapsack whether we consider it or not we call it processed (we don't reconsider). As here we can include that element multiple amount of time then we consider the element not processed if it is considered in the last decision.

### Code changes from \(0/1\) knapsack

In \(0/1\) knapsack once we reject or accept an element we move onto the next element. This is shown in the following code

Recursion of 0/1 Knapsack | |
---|---|

Lines 4, 9 is when we don't consider the element. When we don't consider the element knapsack and unbounded knapsack behaves the same. Hence we don't need any code changes there.

In line \(3\) we are considering the inclusion of the element. Here we change the code for unbounded knapsack. Following is the code for \(0/1\) and unbounded knapsack solved with bottom up approach and their differences marked.

0/1 Knapsack Code (Bottom Up) | |
---|---|

Unbounded Knapsack Code | |
---|---|

Notice when including the element we do not change the `dp[i]`

.

## Rod cutting

Asked in:

### Problem Statement

Given a rod of length \(N\) inches and an array of prices. \(\text{price}[i]\) denotes the value of a piece of length \(i\).

Determine the maximum value obtainable by cutting up the rod and selling the pieces.

### Approach

The approach is same as the unbounded knapsack problem. Think of the total bag weight as rod length \(n\), then you can cut any length \(i\) from \(n\) as long as it is possible. Think of cutting length \(i\) from \(n\) and putting it in a bag. The bag is the storage for all pieces. The pieces of the bag will determine the total profit which we have to maximize.

### Code

## Coin Change II

Find the problem on Leetcode \(\to\)

### Problem Statement

You are given an integer array `coins`

representing coins of different denominations and an integer `amount`

representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin. The answer is guaranteed to fit into a signed 32-bit integer.

### Approach

This is a problem of unbounded knapsack. We have to count number of ways we can place coins to the amount. Think of `amount`

as the bag size, and coins are each element with \(v\) profit, \(v\) is the value of the coin. Similar to unbounded knapsack we can put multiple instances of same coin and fill the bag up i.e, sum up to `amount`

.

### Code

## Coin Change I (Unbounded Knapsack Way)

To solve the problem using most optimal way you can look ðŸ”— here.

Find the problem on leetcode ðŸ”— and gfg ðŸ”—.

### Problem Statement

You are given an integer array `coins`

representing coins of different denominations and an integer `amount`

representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return `-1`

.

You may assume that you have an infinite number of each kind of coin.

### Approach

## Maximum Ribbon Cut

## Comments

This comments system is powered by GitHub Discussions