Learn
Exam

Knapsack Problem 1

Difficulty
BEGINNER

Problem

Given a natural number volume representing the capacity of a knapsack and an array items containing pairs of volume and value for each item, write a solution function that returns the maximum total value achievable by selecting items to place in the knapsack.

If the knapsack contains no items, the maximum value is 0.

Reference

  • The Knapsack Problem is a classic problem where, given a knapsack with a fixed capacity and multiple items (each with a unique volume and value), the goal is to determine a subset of items that maximizes the total value within the knapsack's capacity.

Constraints

  • The knapsack's capacity volume is a natural number not exceeding 100,000.
  • The item information items is a 2D array where each element is a pair [x, y], representing the item's volume x and value y.
    • The length of items is between 1 and 20, inclusive.
    • Both x and y are natural numbers not exceeding 10,000.

Test Case

Test Case Number volume items return
1 23 [[4,1],[9,3],[10,10],[9,8],[5,9]] 20
2 20 [[4,9],[3,3]] 12
3 3 [[4,6],[10,10]] 0

Explanation for Test Case 1

  • For a knapsack with a capacity of 23, the combinations of items that yield the maximum total value are as follows:
    • Selecting Item 1, Item 3, and Item 5:
      • Total volume: 4 + 10 + 5 = 19
      • Total value: 1 + 10 + 9 = 20
    • Selecting Item 2, Item 4, and Item 5:
      • Total volume: 9 + 9 + 5 = 23
      • Total value: 3 + 8 + 9 = 20

Explanation for Test Case 2

  • For a knapsack with a capacity of 20, all items can fit, yielding the maximum total value:
    • Total volume: 4 + 3 = 7
    • Total value: 9 + 3 = 12

Explanation for Test Case 3

  • For a knapsack with a capacity of 3, no items can fit, resulting in a total value of 0.