В задаче о рюкзаке вам необходимо упаковать набор предметов с заданными значениями и размерами (например, весом или объемом) в контейнер максимальной вместимости. Если общий размер предметов превышает вместимость, вы не сможете упаковать их все. В этом случае проблема состоит в том, чтобы выбрать подмножество предметов максимальной общей стоимости, которые поместятся в контейнер.
В следующих разделах показано, как решить задачу о рюкзаке с помощью OR-Tools.
Пример
Вот графическое изображение задачи о рюкзаке:
В приведенной выше анимации 50 предметов упакованы в корзину. Каждый предмет имеет ценность (номер на предмете) и вес (примерно пропорциональный площади предмета). Объявлено, что контейнер имеет вместимость 850 , и наша цель — найти набор предметов, который максимизирует общую ценность, не превышая вместимости.
В следующих разделах описываются программы, решающие задачу о рюкзаке. Полные программы см. в разделе Полные программы .
Импортируйте библиотеки
Следующий код импортирует необходимые библиотеки.
Питон
from ortools.algorithms.python import knapsack_solver
С++
#include <algorithm> #include <cstdint> #include <iterator> #include <numeric> #include <sstream> #include <vector> #include "ortools/algorithms/knapsack_solver.h"
Джава
import com.google.ortools.Loader; import com.google.ortools.algorithms.KnapsackSolver; import java.util.ArrayList;
С#
using System; using Google.OrTools.Algorithms;
Создайте данные
Код ниже создает данные для проблемы.
Питон
values = [
# fmt:off
360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600, 38, 48, 147,
78, 256, 63, 17, 120, 164, 432, 35, 92, 110, 22, 42, 50, 323, 514, 28,
87, 73, 78, 15, 26, 78, 210, 36, 85, 189, 274, 43, 33, 10, 19, 389, 276,
312
# fmt:on
]
weights = [
# fmt: off
[7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15, 42, 9, 0,
42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56, 7, 29, 93, 44, 71,
3, 86, 66, 31, 65, 0, 79, 20, 65, 52, 13],
# fmt: on
]
capacities = [850]С++
std::vector<int64_t> values = {
360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600,
38, 48, 147, 78, 256, 63, 17, 120, 164, 432, 35, 92, 110,
22, 42, 50, 323, 514, 28, 87, 73, 78, 15, 26, 78, 210,
36, 85, 189, 274, 43, 33, 10, 19, 389, 276, 312};
std::vector<std::vector<int64_t>> weights = {
{7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15,
42, 9, 0, 42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56,
7, 29, 93, 44, 71, 3, 86, 66, 31, 65, 0, 79, 20, 65, 52, 13}};
std::vector<int64_t> capacities = {850};Джава
final long[] values = {360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600, 38, 48, 147,
78, 256, 63, 17, 120, 164, 432, 35, 92, 110, 22, 42, 50, 323, 514, 28, 87, 73, 78, 15, 26,
78, 210, 36, 85, 189, 274, 43, 33, 10, 19, 389, 276, 312};
final long[][] weights = {{7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15, 42, 9,
0, 42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56, 7, 29, 93, 44, 71, 3, 86, 66, 31,
65, 0, 79, 20, 65, 52, 13}};
final long[] capacities = {850};С#
long[] values = { 360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600, 38, 48, 147, 78,
256, 63, 17, 120, 164, 432, 35, 92, 110, 22, 42, 50, 323, 514, 28, 87, 73,
78, 15, 26, 78, 210, 36, 85, 189, 274, 43, 33, 10, 19, 389, 276, 312 };
long[,] weights = { { 7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15,
42, 9, 0, 42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56,
7, 29, 93, 44, 71, 3, 86, 66, 31, 65, 0, 79, 20, 65, 52, 13 } };
long[] capacities = { 850 };Данные включают в себя следующее:
-
weights: вектор, содержащий веса элементов. -
values: вектор, содержащий значения элементов. -
capacities: вектор только с одной записью, вместимостью рюкзака.
Объявить решатель
Следующий код объявляет решатель рюкзака, специализированный решатель задач о рюкзаке.
Питон
solver = knapsack_solver.KnapsackSolver(
knapsack_solver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
"KnapsackExample",
)С++
KnapsackSolver solver(
KnapsackSolver::KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
"KnapsackExample");Джава
KnapsackSolver solver = new KnapsackSolver(
KnapsackSolver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, "test");С#
KnapsackSolver solver = new KnapsackSolver(
KnapsackSolver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, "KnapsackExample"); Опция KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER указывает решателю использовать алгоритм ветвей и границ для решения проблемы.
Вызов решателя
Следующий код вызывает решатель и печатает решение.
Питон
solver.init(values, weights, capacities)
computed_value = solver.solve()
packed_items = []
packed_weights = []
total_weight = 0
print("Total value =", computed_value)
for i in range(len(values)):
if solver.best_solution_contains(i):
packed_items.append(i)
packed_weights.append(weights[0][i])
total_weight += weights[0][i]
print("Total weight:", total_weight)
print("Packed items:", packed_items)
print("Packed_weights:", packed_weights)С++
solver.Init(values, weights, capacities);
int64_t computed_value = solver.Solve();
std::vector<int> packed_items;
for (std::size_t i = 0; i < values.size(); ++i) {
if (solver.BestSolutionContains(i)) packed_items.push_back(i);
}
std::ostringstream packed_items_ss;
std::copy(packed_items.begin(), packed_items.end() - 1,
std::ostream_iterator<int>(packed_items_ss, ", "));
packed_items_ss << packed_items.back();
std::vector<int64_t> packed_weights;
packed_weights.reserve(packed_items.size());
for (const auto& it : packed_items) {
packed_weights.push_back(weights[0][it]);
}
std::ostringstream packed_weights_ss;
std::copy(packed_weights.begin(), packed_weights.end() - 1,
std::ostream_iterator<int>(packed_weights_ss, ", "));
packed_weights_ss << packed_weights.back();
int64_t total_weights =
std::accumulate(packed_weights.begin(), packed_weights.end(), int64_t{0});
LOG(INFO) << "Total value: " << computed_value;
LOG(INFO) << "Packed items: {" << packed_items_ss.str() << "}";
LOG(INFO) << "Total weight: " << total_weights;
LOG(INFO) << "Packed weights: {" << packed_weights_ss.str() << "}";Джава
solver.init(values, weights, capacities);
final long computedValue = solver.solve();
ArrayList<Integer> packedItems = new ArrayList<>();
ArrayList<Long> packedWeights = new ArrayList<>();
int totalWeight = 0;
System.out.println("Total value = " + computedValue);
for (int i = 0; i < values.length; i++) {
if (solver.bestSolutionContains(i)) {
packedItems.add(i);
packedWeights.add(weights[0][i]);
totalWeight = (int) (totalWeight + weights[0][i]);
}
}
System.out.println("Total weight: " + totalWeight);
System.out.println("Packed items: " + packedItems);
System.out.println("Packed weights: " + packedWeights);С#
solver.Init(values, weights, capacities);
long computedValue = solver.Solve();
Console.WriteLine("Optimal Value = " + computedValue); Программа сначала инициализирует решатель, а затем вызывает его с помощью computed_value = solver.Solve() . Общее значение оптимального решения — это computed_value , которое в данном случае совпадает с общим весом. Затем программа получает индексы упакованных элементов в решении следующим образом:
packed_items = [x for x in range(0, len(weights[0]))
if solver.BestSolutionContains(x)]Поскольку `solver.BestSolutionContains(x)` возвращает `TRUE`, если элемент x включен в решение, `packed_items` представляет собой список оптимально упакованных элементов. Аналогично, «packed_weights» — это вес упакованных предметов. ### Вывод программы Вот вывод программы.Total value = 7534
Total weight: 850
Packed items: [0, 1, 3, 4, 6, 10, 11, 12, 14, 15, 16, 17, 18, 19, 21, 22, 24, 27, 28, 29, 30, 31,
32, 34, 38, 39, 41, 42, 44, 47, 48, 49]
Packed_weights: [7, 0, 22, 80, 11, 59, 18, 0, 3, 8, 15, 42, 9, 0, 47, 52, 26, 6, 29, 84, 2, 4,
18, 7, 71, 3, 66, 31, 0, 65, 52, 13]
Полные программы
Ниже приведены полные программы, решающие задачу о рюкзаке.
Питон
from ortools.algorithms.python import knapsack_solver
def main():
# Create the solver.
solver = knapsack_solver.KnapsackSolver(
knapsack_solver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
"KnapsackExample",
)
values = [
# fmt:off
360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600, 38, 48, 147,
78, 256, 63, 17, 120, 164, 432, 35, 92, 110, 22, 42, 50, 323, 514, 28,
87, 73, 78, 15, 26, 78, 210, 36, 85, 189, 274, 43, 33, 10, 19, 389, 276,
312
# fmt:on
]
weights = [
# fmt: off
[7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15, 42, 9, 0,
42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56, 7, 29, 93, 44, 71,
3, 86, 66, 31, 65, 0, 79, 20, 65, 52, 13],
# fmt: on
]
capacities = [850]
solver.init(values, weights, capacities)
computed_value = solver.solve()
packed_items = []
packed_weights = []
total_weight = 0
print("Total value =", computed_value)
for i in range(len(values)):
if solver.best_solution_contains(i):
packed_items.append(i)
packed_weights.append(weights[0][i])
total_weight += weights[0][i]
print("Total weight:", total_weight)
print("Packed items:", packed_items)
print("Packed_weights:", packed_weights)
if __name__ == "__main__":
main()С++
#include <algorithm>
#include <cstdint>
#include <iterator>
#include <numeric>
#include <sstream>
#include <vector>
#include "ortools/algorithms/knapsack_solver.h"
namespace operations_research {
void RunKnapsackExample() {
// Instantiate the solver.
KnapsackSolver solver(
KnapsackSolver::KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
"KnapsackExample");
std::vector<int64_t> values = {
360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600,
38, 48, 147, 78, 256, 63, 17, 120, 164, 432, 35, 92, 110,
22, 42, 50, 323, 514, 28, 87, 73, 78, 15, 26, 78, 210,
36, 85, 189, 274, 43, 33, 10, 19, 389, 276, 312};
std::vector<std::vector<int64_t>> weights = {
{7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15,
42, 9, 0, 42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56,
7, 29, 93, 44, 71, 3, 86, 66, 31, 65, 0, 79, 20, 65, 52, 13}};
std::vector<int64_t> capacities = {850};
solver.Init(values, weights, capacities);
int64_t computed_value = solver.Solve();
// Print solution
std::vector<int> packed_items;
for (std::size_t i = 0; i < values.size(); ++i) {
if (solver.BestSolutionContains(i)) packed_items.push_back(i);
}
std::ostringstream packed_items_ss;
std::copy(packed_items.begin(), packed_items.end() - 1,
std::ostream_iterator<int>(packed_items_ss, ", "));
packed_items_ss << packed_items.back();
std::vector<int64_t> packed_weights;
packed_weights.reserve(packed_items.size());
for (const auto& it : packed_items) {
packed_weights.push_back(weights[0][it]);
}
std::ostringstream packed_weights_ss;
std::copy(packed_weights.begin(), packed_weights.end() - 1,
std::ostream_iterator<int>(packed_weights_ss, ", "));
packed_weights_ss << packed_weights.back();
int64_t total_weights =
std::accumulate(packed_weights.begin(), packed_weights.end(), int64_t{0});
LOG(INFO) << "Total value: " << computed_value;
LOG(INFO) << "Packed items: {" << packed_items_ss.str() << "}";
LOG(INFO) << "Total weight: " << total_weights;
LOG(INFO) << "Packed weights: {" << packed_weights_ss.str() << "}";
}
} // namespace operations_research
int main(int argc, char** argv) {
operations_research::RunKnapsackExample();
return EXIT_SUCCESS;
}Джава
package com.google.ortools.algorithms.samples;
import com.google.ortools.Loader;
import com.google.ortools.algorithms.KnapsackSolver;
import java.util.ArrayList;
/**
* Sample showing how to model using the knapsack solver.
*/
public class Knapsack {
private Knapsack() {}
private static void solve() {
KnapsackSolver solver = new KnapsackSolver(
KnapsackSolver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, "test");
final long[] values = {360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600, 38, 48, 147,
78, 256, 63, 17, 120, 164, 432, 35, 92, 110, 22, 42, 50, 323, 514, 28, 87, 73, 78, 15, 26,
78, 210, 36, 85, 189, 274, 43, 33, 10, 19, 389, 276, 312};
final long[][] weights = {{7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15, 42, 9,
0, 42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56, 7, 29, 93, 44, 71, 3, 86, 66, 31,
65, 0, 79, 20, 65, 52, 13}};
final long[] capacities = {850};
solver.init(values, weights, capacities);
final long computedValue = solver.solve();
ArrayList<Integer> packedItems = new ArrayList<>();
ArrayList<Long> packedWeights = new ArrayList<>();
int totalWeight = 0;
System.out.println("Total value = " + computedValue);
for (int i = 0; i < values.length; i++) {
if (solver.bestSolutionContains(i)) {
packedItems.add(i);
packedWeights.add(weights[0][i]);
totalWeight = (int) (totalWeight + weights[0][i]);
}
}
System.out.println("Total weight: " + totalWeight);
System.out.println("Packed items: " + packedItems);
System.out.println("Packed weights: " + packedWeights);
}
public static void main(String[] args) throws Exception {
Loader.loadNativeLibraries();
Knapsack.solve();
}
}С#
using System;
using Google.OrTools.Algorithms;
public class Knapsack
{
static void Main()
{
KnapsackSolver solver = new KnapsackSolver(
KnapsackSolver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, "KnapsackExample");
long[] values = { 360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600, 38, 48, 147, 78,
256, 63, 17, 120, 164, 432, 35, 92, 110, 22, 42, 50, 323, 514, 28, 87, 73,
78, 15, 26, 78, 210, 36, 85, 189, 274, 43, 33, 10, 19, 389, 276, 312 };
long[,] weights = { { 7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15,
42, 9, 0, 42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56,
7, 29, 93, 44, 71, 3, 86, 66, 31, 65, 0, 79, 20, 65, 52, 13 } };
long[] capacities = { 850 };
solver.Init(values, weights, capacities);
long computedValue = solver.Solve();
Console.WriteLine("Optimal Value = " + computedValue);
}
}