بالنسبة إلى مشكلة في حقيبة الظهر، يجب وضع مجموعة من العناصر مع قيم وأحجام محدّدة (مثل الأوزان أو الأحجام) في حاوية بأقصى سعة. إذا كان إجمالي حجم السلع يتجاوز الحدّ الأقصى، لا يمكنك تغليفها جميعًا. في هذه الحالة، تكمن المشكلة في اختيار مجموعة فرعية من عناصر الحد الأقصى لإجمالي القيمة التي تتناسب مع الحاوية.
توضح الأقسام التالية كيفية حل مشكلة حقيبة الظهر باستخدام أدوات OR.
مثال
في ما يلي تصوير رسومي لمشكلة في حقيبة الظهر:
في الصورة المتحركة أعلاه، يتم تجميع 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);
}
}