नैपसैक समस्या

नैपसैक की समस्या में, आपको दी गई वैल्यू के हिसाब से आइटम का एक सेट पैक करना होगा और साइज़ (जैसे कि वज़न या वॉल्यूम), ज़्यादा से ज़्यादा क्षमता वाले कंटेनर में को अपनाएं. अगर आइटम का कुल साइज़, तय सीमा से ज़्यादा है, तो सभी को पैक नहीं किया जा सकता. इस मामले में समस्या यह है कि ज़्यादा से ज़्यादा कुल वैल्यू वाले आइटम का एक सबसेट चुना जाए कंटेनर में फ़िट हो जाएगा.

नीचे दिए गए सेक्शन में 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 विकल्प, सॉल्वर को यह बताता है सवाल को हल करने के लिए, ब्रांच और बाउंड एल्गोरिदम का इस्तेमाल करें.

ध्यान दें: CP-SAT सॉल्वर की तरह, नैपसैक सॉल्वर भी पूर्णांकों के साथ काम करता है. इसलिए प्रोग्राम के डेटा में सिर्फ़ पूर्णांक शामिल हो सकते हैं. अगर आपकी समस्या में गैर-पूर्णांक मान है, तो आप काफ़ी बड़े पूर्णांक में डेटा का इस्तेमाल करता है. यह रही नॉन-इंटीजर कंस्ट्रेंट को बदलने का उदाहरण

सॉल्वर को कॉल करें

यहां दिया गया कोड, सॉल्वर को कॉल करता है और समाधान को प्रिंट करता है.

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.Best समाधानContains(x)` आइटम x शामिल होने पर `TRUE` लौटाता है समाधान में, `pack_items` सबसे अच्छे पैक किए गए आइटम की सूची है. इसी तरह, `pack_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);
    }
}