✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-175

Unbounded Knapsack Problem

Explore an optimization problem in which each available item type can be selected repeatedly to maximize value within a fixed capacity.

Explanation

Overview

The Unbounded Knapsack Problem is a variation of the knapsack problem in which unlimited copies of each item type are available. The objective is to maximize total value without exceeding the knapsack capacity.

Key concepts

Unlimited item reuse; Optimal substructure; Capacity-based states; State transitions; Ascending capacity iteration

Variables

w: The current knapsack capacity being considered.; weight[i]: The weight of item type i.; value[i]: The value of one copy of item type i.; dp[w]: The maximum achievable value for capacity w.

Complexity

tabulation: O(nW) time and O(W) space.; variables: n is the number of item types and W is the integer capacity.

Example

items: name: A; weight: 2; value: 3; name: B; weight: 3; value: 5; capacity: 6; selectedItems: B; B; totalWeight: 6; maximumValue: 10; explanation: Two copies of item B fit exactly into the capacity and produce a total value of 10.

Pseudocode

function unboundedKnapsack(weights, values, n, capacity):
dp = array of size capacity + 1 filled with 0
for w = 1 to capacity:
for i = 0 to n - 1:
if weights[i] <= w:
dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
return dp[capacity]

Applications

Inventory selection.; Cutting and manufacturing decisions.; Resource allocation.; Repeated product selection.; Production planning.

Variables

W

The current knapsack capacity being considered.

Weight[i]

The weight of item type i.

Value[i]

The value of one copy of item type i.

Dp[w]

The maximum achievable value for capacity w.

Example or application

Items

NameWeightValue

A

2

3

B

3

5

Capacity

6

Selected Items

  • B

  • B

Total Weight

6

Maximum Value

10

Explanation

Two copies of item B fit exactly into the capacity and produce a total value of 10.

Definition

The Unbounded Knapsack Problem is a variation of the knapsack problem in which unlimited copies of each item type are available. The objective is to maximize total value without exceeding the knapsack capacity.

Mathematical Representation

dp[w] = max(dp[w], value[i] + dp[w - weight[i]]) for every item i whose weight does not exceed w.

Approaches

Recursive

At each state, consider selecting an available item and solving the remaining capacity, allowing the same item type to appear again.

Memoization

Stores the best result for each remaining capacity.

Tabulation

Builds solutions for increasing capacities while considering every item type.

Capacity Ascending

In a one-dimensional implementation, processes capacities in ascending order so an item can be reused during the same iteration.

Pseudocode

function unboundedKnapsack(weights, values, n, capacity):
dp = array of size capacity + 1 filled with 0
for w = 1 to capacity:
for i = 0 to n - 1:
if weights[i] <= w:
dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
return dp[capacity]

Complexity

Tabulation

O(nW) time and O(W) space.

Variables

n is the number of item types and W is the integer capacity.

Key Concepts

  • Unlimited item reuse

  • Optimal substructure

  • Capacity-based states

  • State transitions

  • Ascending capacity iteration

Advantages

  • Models situations where resources or products can be selected repeatedly.

  • Uses dynamic programming to avoid redundant calculations.

  • Can be implemented with a one-dimensional array.

  • Provides a flexible optimization model for repeated choices.

Limitations

  • The O(nW) approach is pseudo-polynomial.

  • Large capacities can require substantial computation.

  • The standard model assumes item weights and capacity are nonnegative integers.

  • Zero-weight positive-value items can make the mathematical problem unbounded and must be handled separately.

Applications

  • Inventory selection.

  • Cutting and manufacturing decisions.

  • Resource allocation.

  • Repeated product selection.

  • Production planning.

Related Topics

  • 0/1 Knapsack Problem

  • Coin Change Problem

  • Rod Cutting Problem

  • Dynamic Programming

Practice Question

What is the main difference between 0/1 Knapsack and Unbounded Knapsack?

Practice Answer

0/1 Knapsack permits each item at most once, while Unbounded Knapsack permits unlimited copies of each item type.

Learning Objectives

  • Explain the central idea and purpose of unbounded knapsack problem.

  • Identify the assumptions, inputs, and conditions relevant to unbounded knapsack problem.

  • Evaluate an application of unbounded knapsack problem for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Dynamic Programming Applications

Suggest a correction or source · More in Algorithms & Data Structures