knaptime/zeroone/
mod.rs

1//! # 0-1 Knapsack
2//! A variant of the knapsack problem.
3//!
4//! Given a list of items with associated weights and values, choose at most one of each given item.
5//! Maximize the value while ensuring the weight less than or equal to a given capacity.
6//!
7//! Possible optimizations:
8//! - Sliding (similar to [dpsliding](crate::dpsliding))
9//! - Walkback
10//!     - This is a bit more nuanced than sliding.
11//!     - Sort the items from large to small to minimize the number of marked squares.
12//!     - Use the existing markings and combine them with each item in the table to get the row markings.
13
14pub mod dp;
15pub mod recursive;