क्नैक्सैक प्रॉब्लम में, आपको ज़्यादा से ज़्यादा क्षमता वाले कंटेनर में, दी गई वैल्यू और साइज़ (जैसे कि वज़न या वॉल्यूम) के साथ सामान का एक सेट पैक करना होता है. अगर सामान का कुल साइज़, तय सीमा से ज़्यादा है, तो उन सभी को पैक नहीं किया जा सकता. इस मामले में, समस्या यह है कि कंटेनर में फ़िट हो सकने वाले कुल मान के आइटम का एक सबसेट चुना जाए.
नीचे दिए गए सेक्शन में, 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)]अगर समाधान में शामिल करने के लिए आइटम x शामिल है, तो `solver.BestSolutionContains(x)`, `TRUE` दिखाता है. `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); } }