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. }
Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License, and code samples are licensed under the Apache 2.0 License. For details, see the Google Developers Site Policies. Java is a registered trademark of Oracle and/or its affiliates.
Last updated 2024-08-06 UTC.
[null,null,["Last updated 2024-08-06 UTC."],[[["\u003cp\u003eThis 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.\u003c/p\u003e\n"],["\u003cp\u003eIt handles fractional profits and weights, aiming to select a subset of items that maximize profit without exceeding the knapsack's capacity.\u003c/p\u003e\n"],["\u003cp\u003eThe library provides access to the solution and relevant classes like \u003ccode\u003eKnapsackSolverForCuts\u003c/code\u003e for utilizing its functionality.\u003c/p\u003e\n"],["\u003cp\u003eNote: It currently uses 'double' for profits and weights, with plans to merge it with \u003ccode\u003ealgorithms/knapsack_solver\u003c/code\u003e which utilizes 'int64_t'.\u003c/p\u003e\n"]]],["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"],null,["# knapsack_solver_for_cuts\n\nC++ Reference: knapsack_solver_for_cuts\n=======================================\n\n\nNote: This documentation is automatically generated.\nThis 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. \n\nGiven 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. \n\nFrom a mathematical point of view, the one-dimensional knapsack problem can be modeled by linear constraint: Sum(i:1..n)(weight_i \\* item_i) \\\u003c= c, where item_i is a 0-1 integer variable. The goal is to maximize: Sum(i:1..n)(profit_i \\* item_i). \n\nExample Usage: std::vector\\\u003cdouble\\\u003e profits = {0, 0.5, 0.4, 1, 1, 1.1}; std::vector\\\u003cdouble\\\u003e 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\\\u003cTimeLimit\\\u003e time_limit = absl::make_unique\\\u003cTimeLimit\\\u003e(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 \\\u003c number_of_items; ++item_id) { solver.best_solution(item_id); // Access the solution. } \n\n| Classes ------- ||\n|--------------------------------------------------------------------------------------------------------------------|---|\n| [KnapsackPropagatorForCuts](/optimization/reference/algorithms/knapsack_solver_for_cuts/KnapsackPropagatorForCuts) |\n| [KnapsackSearchNodeForCuts](/optimization/reference/algorithms/knapsack_solver_for_cuts/KnapsackSearchNodeForCuts) |\n| [KnapsackSearchPathForCuts](/optimization/reference/algorithms/knapsack_solver_for_cuts/KnapsackSearchPathForCuts) |\n| [KnapsackSolverForCuts](/optimization/reference/algorithms/knapsack_solver_for_cuts/KnapsackSolverForCuts) |\n| [KnapsackStateForCuts](/optimization/reference/algorithms/knapsack_solver_for_cuts/KnapsackStateForCuts) |"]]
