A library for solving the 0-1 knapsack problem (inspired by https://rosettacode.org/wiki/Knapsack_problem/0-1#Swift )

Example.swift

/// An example implementation of the `KnapsackItem` protocol.
struct Example: KnapsackItem, CustomStringConvertible {
    var name: String
    
    var weight: Int
    var value: Int
    
    var description: String { name }
}

let problemSetting = ZeroOneKnapsackProblem(with: [
        Example(name: "map",                    weight: 9,   value: 150),
        Example(name: "compass",                weight: 13,  value: 35),
        Example(name: "water",                  weight: 153, value: 200),
        Example(name: "sandwich",               weight: 50,  value: 160),
        Example(name: "glucose",                weight: 15,  value: 60),
        Example(name: "tin",                    weight: 68,  value: 45),
        Example(name: "banana",                 weight: 27,  value: 60),
        Example(name: "apple",                  weight: 39,  value: 40),
        Example(name: "cheese",                 weight: 23,  value: 30),
        Example(name: "beer",                   weight: 52,  value: 10),
        Example(name: "suntan cream",           weight: 11,  value: 70),
        Example(name: "camera",                 weight: 32,  value: 30),
        Example(name: "t-shirt",                weight: 24,  value: 15),
        Example(name: "trousers",               weight: 48,  value: 10),
        Example(name: "umbrella",               weight: 73,  value: 40),
        Example(name: "waterproof trousers",    weight: 42,  value: 70),
        Example(name: "waterproof overclothes", weight: 43,  value: 75),
        Example(name: "note-case",              weight: 22,  value: 80),
        Example(name: "sunglasses",             weight: 7,   value: 20),
        Example(name: "towel",                  weight: 18,  value: 12),
        Example(name: "socks",                  weight: 4,   value: 50),
        Example(name: "books",                  weight: 30,  value: 10),
    ],
    computeResultsUpTo: 400)
let result = problemSetting(limit: 400)
let (totalValue, totalWeight) = (result.value, result.weight)
print("Kept:")
result.contents.forEach { print("  \($0)") }
print("For a total value of \(totalValue) and a total weight of \(totalWeight)")

Main.swift

// MARK: Overview
// This library solves the 0-1 Knapsack problem, aiming to pack a
// knapsack from an array of items which have a weight and a value, so
// that the sum of the values of the items in the knapsack is as high as
// possible and the sum of the weight of the items in the knapsack does
// not exceed a certain limit.

// This library provides a `KnapsackItem` protocol, allowing the user to
// extend any class, struct or enum to be used as items that may be part
// of the knapsack.

// In order to solve the problem, this library provides the
// `ZeroOneKnapsackProblem` class, whose purpose is to serve as a
// representation of the problem, and whose main functionality is to
// find a solution to the problem using the dynamic programming
// algorithm found at:
// https://rosettacode.org/wiki/Knapsack_problem/0-1#Swift
// and to return its result to the user, while internally storing its
// calculations into a result table to avoid re-calculating intermediary
// results when the size of the knapsack changes or when the item pool
// differs slightly.
// It uses a nested type (`Knapsack`) in order to represent a solution
// to the problem for a given limit.
// It provides the `solve(until:)` method to fill the result table with
// intermediary values for filling the knapsack for a given limit, and
// the `solution(for:)` method from fetching the solution to the problem
// for a given limit, as well as many convenience functions which
// allows to get the solution to the problem by combining the previous
// two methods if deferring the building of the result table and the
// fetching of the result is unnecessary, as well as variants of those
// methods which returns the solution as an `Array` of `Item`s instead.

// MARK: - Code

/// Holds an item for solving the Knapsack problem.
public protocol KnapsackItem {
    /// The space taken by the item in the knapsack.
    var weight: Int { get }

    /// The item is more likely to be included when the ratio
    /// between the value and the weight of the item is high.
    var value:  Int { get }
}


/// A class built for solving the 0-1 variant of the Knapsack
/// problem using dynamic programming and memoization.
/// The 0-1 Knapsack problem solver seeks to pack a knapsack from a list
/// of items whose total weight does not exceed a given limit, while
/// having the greatest total value in the knapsack.
/// - SeeAlso: `KnapsackItem`
final public class ZeroOneKnapsackProblem<Item: KnapsackItem> {
    /// A list of items that can appear as
    /// part of a solution to the problem.
    /// - SeeAlso: `KnapsackItem`
    public let items: [Item]

    /// Holds the results to the Knapsack problem.
    /// Each row represents an item from `items`.
    /// Each column represents a maximum limit.
    var resultTable: [[Int]]

    /// The largest limit where the solution to the
    /// Knapsack problem has already been computed.
    public var solvedLimit: Int

    /// Holds the optimal solution to the 0-1 Knapsack problem
    /// for a given `problemSetting` and a given `limit`.
    public struct Knapsack: KnapsackItem {
        /// An object representing the problem of which `Result` is a
        /// solution.
        public let problemSetting: ZeroOneKnapsackProblem<Item>

        /// The items stored in the knapsack.
        public let contents: [Item]

        /// The maximum weight that can be stored in the knapsack.
        public let capacity: Int

        /// The sum of the `weight`s of each `Item`.
        /// - Complexity: O(1)
        public let weight: Int

        /// The sum of the `value`s of each `Item`.
        /// - Complexity: O(n) where n is the number of items in `items`
        public var value: Int { contents.reduce(0) { $0 + $1.value } }

        init(solutionTo problem: ZeroOneKnapsackProblem<Item>,
             containing items: [Item], capacity: Int, totalWeight: Int) {
            assert(0...capacity ~= totalWeight)
            self.problemSetting = problem
            self.contents = items
            (self.capacity, self.weight) = (capacity, totalWeight)
        }
    }

    /// Sets up the class for solving the 0-1 Knapsack problem,
    /// allocating enough space in the result table to compute
    /// the result for limits less than or equal to maxLimit.
    public init(with items: [Item], reserveCapacityFor maxLimit: Int? = nil) {
        precondition((maxLimit ?? 0) >= 0)
        precondition(items.allSatisfy { $0.weight >= 0 })
        self.items = items
        self.resultTable = (0...items.count).map { _ in
            var res = [0]
            if let maxLimit = maxLimit {
                res.reserveCapacity(maxLimit + 1)
            }
            return res
        }
        self.solvedLimit = 0
    }
}


// Convenience init
public extension ZeroOneKnapsackProblem {
    /// Sets up the class for solving the 0-1 Knapsack problem,
    /// computing the results for limits less than or equal to limit.
    convenience init(with items: [Item], computeResultsUpTo limit: Int) {
        self.init(with: items, reserveCapacityFor: limit)
        solve(until: limit)
    }
}


// Solver
extension ZeroOneKnapsackProblem {
    func extendResultTable(by limit: Int) {
        guard limit > solvedLimit else {
            // No need to extend the result table, the table's first
            // row already contains enough elements to build it.
            return
        }
        // Don't forget to extend the null
        // row of the result table as well.
        resultTable[0] += [Int](repeating: 0, count: limit - solvedLimit)
        solvedLimit = limit
    }

    /// Solves the 0-1 Knapsack problem for
    /// limits less than or equal to limit.
    public func solve(until limit: Int) {
        guard limit > solvedLimit else {
            // Already solved for the given limit.
            return
        }
        extendResultTable(by: limit)
        items.enumerated().forEach { fill(&resultTable[$0.0], $0) }
    }

    func fill(_ curr: inout [Int], _ pair: (Int, Item)) {
        let (i, item) = pair
        let prev = resultTable[i]
        let unfilledIndices = prev.suffix(from: curr.endIndex)
        
        for currentCapacity in unfilledIndices {
            let valueWithoutItem = prev[currentCapacity]
            let itemFitsInKnapsack = item.weight <= currentCapacity
            guard itemFitsInKnapsack else {
                // The item is too heavy to be included in the knapsack
                // thus the value of the knapsack doesn't change.
                curr.append(valueWithoutItem)
                continue
            }
            // Add the item to the knapsack if doing so increases its
            // value, and add the knapsack's value to the result table.
            let valueWithItem = prev[currentCapacity-item.weight] + item.value
            curr.append(max(valueWithoutItem, valueWithItem))
        }
    }
}


// Various methods for fetching results from the result table.
public extension ZeroOneKnapsackProblem {
    /// Gets the solution to the problem if it has
    /// already been solved for the given limit.
    /// - Returns:
    /// A knapsack representing the optimal solution to the problem
    /// if it is already included in `resultTable`, `nil` otherwise.
    /// - Complexity:
    /// Constant time (O(1)) if the limit is not included in the result
    /// table, linear time (O(n)) otherwise, where n is the number of
    /// items.
    func solution(for limit: Int) -> Knapsack? {
        let hasBeenSolved = 0...solvedLimit ~= limit
        guard hasBeenSolved else {
            // You need to call solve(until: limit) first.
            return nil
        }

        var remainingWeight = limit

        // An iterator yielding a tuple whose right element goes through
        // all the rows of the table but the last one, and whose left
        // element is the row next to the left element's.
        let tableRowIterator = zip(resultTable, resultTable.dropFirst())

        var result = [Item]()
        for (item, row) in zip(items, tableRowIterator).reversed() {
            let valueWithItem = row.0[remainingWeight]
            let valueWithoutItem = row.1[remainingWeight]
            
            let isWorthAddingToKnapsack = valueWithItem != valueWithoutItem
            guard isWorthAddingToKnapsack else {
                continue
            }
            
            remainingWeight -= item.weight
            result.append(item)
            
            let knapsackIsFull = remainingWeight == 0
            if knapsackIsFull {
                break
            }
        }
        
        let weight = limit - remainingWeight
        return Knapsack(solutionTo: self, containing: result, capacity: limit, totalWeight: weight)
    }

    /// Gets the set of items included in the solution to the problem
    /// if it has already been solved for the given limit.
    /// - Returns:
    /// A `Set` of `Item`s in the optimal solution to the problem if it
    /// is already included in `resultTable`, `nil` otherwise.
    /// - Complexity:
    /// Constant time (O(1)) if the limit is not included in the result
    /// table, linear time (O(n) where n is the number of
    /// items in the item pool).
    func result(for limit: Int) -> [Item]? {
        solution(for: limit)?.contents
    }

    /// Gets the solution to the problem, calculating it if necessary.
    /// - Precondition: `limit` must be positive.
    /// - Returns:
    /// A knapsack representing the optimal solution to the problem.
    /// - Complexity:
    /// Linear time (O(n)) where n is the number of items
    /// in the item pool.
    /// - SeeAlso: `solveAndGetSolution(for:)`
    func callAsFunction(limit: Int) -> Knapsack {
        solveAndGetSolution(for: limit)
    }

    /// Gets the solution to the problem, calculating it if necessary.
    /// - Precondition: `limit` must be positive.
    /// - Returns:
    /// A knapsack representing the optimal solution to the problem.
    func solveAndGetSolution(for limit: Int) -> Knapsack {
        precondition(limit >= 0)
        solve(until: limit)
        return solution(for: limit)!
    }

    /// Gets the set of items included in the solution to the problem,
    /// calculating it if necessary.
    /// - Precondition: `limit` must be positive.
    /// - Returns:
    /// A `Set` of `Item`s in the optimal solution to the problem.
    func solveAndGetResult(for limit: Int) -> [Item] {
        solveAndGetSolution(for: limit).contents
    }
}