במקרה של בעיה בתיק, אתם צריכים לארוז יחד כל פריט תוכן את הערכים והגדלים שבחרתם (למשל, משקל או נפחים) בקונטיינר עם קיבולת מקסימלית. אם הנפח הכולל של הפריטים חורג מהקיבולת, לא תוכלו לארוז את כולם. במקרה כזה, הבעיה היא לבחור קבוצת משנה של הפריטים שהערך הכולל המקסימלי יתאים למאגר.
הקטעים הבאים מסבירים איך לפתור בעיה של תיק גב באמצעות OR-Tools.
דוגמה
הנה דוגמה גרפית לבעיה בתיק גב:
באנימציה שלמעלה, 50 פריטים מסודרים בפח אשפה. לכל פריט יש ערך (המספר על הפריט) ומשקל (יחסית לאזור של הפריט).
ההצהרה על קיבולת הפריטים היא 850, והמטרה שלנו היא למצוא קבוצה של פריטים למיקסום הערך הכולל, מבלי לחרוג מהקיבולת.
בחלקים הבאים מתוארות תוכניות לפתרון בעיות שקשורות לתיק גב. התוכניות המלאות זמינות במאמר השלמת התוכניות.
ייבוא הספריות
הקוד הבא מייבא את הספריות הנדרשות.
Python
from ortools.algorithms.python import knapsack_solver
C++
#include <algorithm> #include <cstdint> #include <iterator> #include <numeric> #include <sstream> #include <vector> #include "ortools/algorithms/knapsack_solver.h"
Java
import com.google.ortools.Loader; import com.google.ortools.algorithms.KnapsackSolver; import java.util.ArrayList;
C#
using System; using Google.OrTools.Algorithms;
יצירת הנתונים
הקוד הבא יוצר את הנתונים עבור הבעיה.
Python
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]
C++
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};
Java
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};
C#
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: וקטור עם כניסה אחת בלבד, הקיבולת של התיק.
הצהרה על הפתרון
הקוד הבא מצהיר על הכלי לפתרון תרמיל ההכנה: פתרון יעיל לבעיות בתיק.
Python
solver = knapsack_solver.KnapsackSolver(
knapsack_solver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
"KnapsackExample",
)
C++
KnapsackSolver solver(
KnapsackSolver::KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
"KnapsackExample");
Java
KnapsackSolver solver = new KnapsackSolver(
KnapsackSolver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, "test");
C#
KnapsackSolver solver = new KnapsackSolver(
KnapsackSolver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, "KnapsackExample");
האפשרות KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER מורה לפותר הבעיות להשתמש באלגוריתם הסתעפות וההתחייבות כדי לפתור את הבעיה.
התקשרות לפותר הבעיות
הקוד הבא מתקשר לפותר הבעיות ומדפיס את הפתרון.
Python
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)
C++
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() << "}";
Java
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);
C#
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]
השלמת התוכניות
כאן מוצגות התוכניות המלאות לפתרון הבעיה בתיק הנשיאה.
Python
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()
C++
#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;
}
Java
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();
}
}
C#
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);
}
}