Sırt çantasıyla ilgili sorunda, belirli değerler ve boyutlarla (örneğin, ağırlıklar veya hacimler) bir öğe grubunu maksimum kapasiteye sahip bir pakete paketlemeniz gerekir. Öğelerin toplam boyutu kapasiteyi aşıyorsa hepsini paketleyemezsiniz. Bu durumda sorun, kapsayıcıya sığacak maksimum toplam değerin bir alt kümesini seçmektir.
Aşağıdaki bölümlerde, OR-Araçları kullanılarak sızdırılma sorununu nasıl çözebileceğiniz gösterilmektedir.
Örnek
Sırt çantasıyla ilgili problemin grafik tasviri:
Yukarıdaki animasyonda 50
öğe çöp kutusuna paketlenmiştir. Her öğenin bir değeri (öğedeki sayı) ve bir ağırlığı (öğenin alanıyla yaklaşık olarak orantılıdır) vardır.
Kutunun kapasitesi 850
olduğu iddia edilir ve amacımız, kapasiteyi aşmadan toplam değeri en üst düzeye çıkaracak öğe grubunu bulmaktır.
Aşağıdaki bölümlerde, dinleme sorunu sorununu çözen programlar açıklanmaktadır. Programların tamamı için Tamamlanan programlar başlıklı makaleyi inceleyin.
Kitaplıkları içe aktar
Aşağıdaki kitaplıkta gerekli kitaplıkları içe aktarılmaktadır.
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;
Verileri oluşturma
Aşağıdaki kod, sorunla ilgili verileri oluşturur.
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 };
Bu veriler aşağıdakileri içerir:
weights
: Öğelerin ağırlıklarını içeren bir vektördür.values
: Öğelerin değerlerini içeren bir vektördür.capacities
: Tek girişe ve sırt çantasının kapasitesine sahip bir vektör.
Çözümleyiciyi bildirme
Aşağıdaki kod, sırt çantası problemleri için özel bir çözümleyici olan sırt çantası çözücüyü göstermektedir.
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
seçeneği, problem çözücüye sorunu çözmek için şube ve bağlı algoritmasını kullanmasını söyler.
Çözümleyiciyi arayın
Aşağıdaki kod çözücüyü çağırır ve çözümü yazdırır.
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);
Program, ilk olarak çözümleyiciyi başlatır ve ardından computed_value = solver.Solve()
tarihine kadar çağırır.
İdeal çözümün toplam değeri computed_value
, yani bu senaryodaki toplam ağırlığın toplamıdır. Ardından program, çözümdeki paketlenmiş öğelerin
dizinlerini aşağıdaki gibi alır:
packed_items = [x for x in range(0, len(weights[0])) if solver.BestSolutionContains(x)]xsol öğesi çözüme dahil edilirse "solver.BestSolutionContains(x)" işlevi "TRUE" değerini döndürür. Bu nedenle "packed_items", en uygun paketlenmiş öğelerin listesidir. Benzer şekilde, "paketlenmiş_ağırlıklar", paketlenen öğelerin ağırlıklarıdır. ### Program çıkışı Programın çıktısını aşağıda görebilirsiniz.
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]
Tamamlanan programlar
Aşağıdaki sırt çantası problemini çözen programların tamamı aşağıda verilmiştir.
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); } }