Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class BasicKnapsackSolver
Note: This documentation is automatically generated.
Use Dynamic programming to solve a single knapsack. This is used by the
presolver to simplify variables appearing in a single linear constraint.
Complexity is the best of
- O(num_variables * num_relevant_values ^ 2) or
- O(num_variables * num_relevant_values * max_domain_size).
| Method |
Solve | Return type: Result Arguments: const std::vector<Domain>& domains,
const std::vector<int64_t>& coeffs,
const std::vector<int64_t>& costs, const Domain& rhs |
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\u003eThe \u003ccode\u003eBasicKnapsackSolver\u003c/code\u003e utilizes dynamic programming to address the single knapsack problem, simplifying variables within a single linear constraint during presolving.\u003c/p\u003e\n"],["\u003cp\u003eThe solver boasts a complexity that is determined by the most efficient option between O(num_variables * num_relevant_values ^ 2) and O(num_variables * num_relevant_values * max_domain_size).\u003c/p\u003e\n"],["\u003cp\u003eA \u003ccode\u003eSolve\u003c/code\u003e method is provided, accepting domains, coefficients, costs, and a right-hand side to compute a solution.\u003c/p\u003e\n"]]],["The `BasicKnapsackSolver` class utilizes dynamic programming to solve a single knapsack problem. It simplifies variables in single linear constraints, with a time complexity of either O(num_variables * num_relevant_values ^ 2) or O(num_variables * num_relevant_values * max_domain_size). The primary action is performed by the `Solve` method, which accepts vectors of domains, coefficients, costs, and a right-hand side domain (`rhs`) as input and returns a `Result`.\n"],null,["# BasicKnapsackSolver\n\nC++ Reference: class BasicKnapsackSolver\n========================================\n\n\nNote: This documentation is automatically generated.\nUse Dynamic programming to solve a single knapsack. This is used by the presolver to simplify variables appearing in a single linear constraint. \n\nComplexity is the best of \n- O(num_variables \\* num_relevant_values \\^ 2) or \n- O(num_variables \\* num_relevant_values \\* max_domain_size).\n\n| Method ||\n|---------------------------------------------------------------------------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------|\n| [`Solve`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/util.h#L244) | Return type: `Result ` Arguments: `const std::vector\u003cDomain\u003e& domains, const std::vector\u003cint64_t\u003e& coeffs, const std::vector\u003cint64_t\u003e& costs, const Domain& rhs` \u003cbr /\u003e |"]]
