Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: knapsack_solver_for_cuts
Note: This documentation is automatically generated.
This library solves 0-1 one-dimensional knapsack problems with fractional profits and weights using the branch and bound algorithm. Note that algorithms/knapsack_solver uses 'int64_t' for the profits and the weights. TODO(user): Merge this code with algorithms/knapsack_solver.
Given n items, each with a profit and a weight and a knapsack of capacity c, the goal is to find a subset of the items which fits inside c and maximizes the total profit. Without loss of generality, profits and weights are assumed to be positive.
From a mathematical point of view, the one-dimensional knapsack problem can be modeled by linear constraint: Sum(i:1..n)(weight_i * item_i) <= c, where item_i is a 0-1 integer variable. The goal is to maximize: Sum(i:1..n)(profit_i * item_i).
Example Usage: std::vector<double> profits = {0, 0.5, 0.4, 1, 1, 1.1}; std::vector<double> weights = {9, 6, 2, 1.5, 1.5, 1.5}; KnapsackSolverForCuts solver("solver"); solver.Init(profits, weights, capacity); bool is_solution_optimal = false; std::unique_ptr<TimeLimit> time_limit = absl::make_unique<TimeLimit>(time_limit_seconds); // Set the time limit. const double profit = solver.Solve(time_limit.get(), &is_solution_optimal); const int number_of_items(profits.size()); for (int item_id(0); item_id < number_of_items; ++item_id) { solver.best_solution(item_id); // Access the solution. }
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-06 UTC."],[[["This C++ library employs a branch and bound algorithm to solve 0-1 one-dimensional knapsack problems, optimizing for maximum profit within a given capacity constraint."],["It handles fractional profits and weights, aiming to select a subset of items that maximize profit without exceeding the knapsack's capacity."],["The library provides access to the solution and relevant classes like `KnapsackSolverForCuts` for utilizing its functionality."],["Note: It currently uses 'double' for profits and weights, with plans to merge it with `algorithms/knapsack_solver` which utilizes 'int64_t'."]]],["This library utilizes the branch and bound algorithm to solve 0-1 one-dimensional knapsack problems with fractional profits and weights. The goal is to maximize the total profit of a subset of items while ensuring their combined weight does not exceed the knapsack's capacity. The `KnapsackSolverForCuts` class is used, initialized with profits, weights, and capacity. The `Solve` function is used to determine the profit. The items included in the solution can be obtained with the `best_solution` function.\n"]]
