liveBook · Manning

Item indivisibility

As explained in Algorithms Every Programmer Should Know

Item indivisibility is the condition that each item must be selected as a whole rather than divided into fractional portions.

Item indivisibility means selecting each item completely or not selecting it at all. This whole-item constraint defines the 0/1 Knapsack problem and makes locally attractive choices potentially waste capacity. section 7.3 section 7.4

The constraint changes both the strategy and the implementation:

  • Rejects a simple greedy choice: taking the best value-per-weight item first can leave unusable gaps and reduce the global result. section 7.3
  • Requires comparing two alternatives for each item: skip it, or take it and combine its value with the best result for the remaining capacity. section 7.4
  • Supports a two-dimensional dynamic-programming matrix for clear tracing, or a one-dimensional array when memory use matters. section 7.3

Whole items versus divisible materials

A packaged object must enter the container whole or stay out, so the 0/1 model applies. Liquid fuel, bulk grain, or loose material can be divided; fractional knapsack can sort by value-per-weight and take an exact fraction of the final item. section 7.3 section 7.4

How Algorithms Every Programmer Should Know covers it

How deep it goes
Explains greedy failure, the skip-or-take recurrence, matrix storage, and one-dimensional space optimization.
Examples
Contrasts packaged objects with divisible liquids, grains, and loose materials.
What you can do after
Evaluate/understand when whole-item constraints require 0/1 knapsack instead of fractional knapsack.
How it connects
Connects 0/1 knapsack with fractional knapsack, greedy algorithms, dynamic programming, and space optimization.

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.