এই পৃষ্ঠাটি Cloud Translation API অনুবাদ করেছে।

ন্যাপস্যাক সমস্যা

ন্যাপস্যাকের সমস্যায় , আপনাকে প্রদত্ত মান এবং মাপ (যেমন ওজন বা ভলিউম) সহ একটি সর্বাধিক ক্ষমতা সহ একটি পাত্রে আইটেমগুলির একটি সেট প্যাক করতে হবে। আইটেমগুলির মোট আকার ধারণক্ষমতা অতিক্রম করলে, আপনি সেগুলি সব প্যাক করতে পারবেন না। সেই ক্ষেত্রে, সমস্যা হল সর্বাধিক মোট মূল্যের আইটেমগুলির একটি উপসেট বেছে নেওয়া যা কন্টেইনারে ফিট হবে।

নিম্নলিখিত বিভাগগুলি দেখায় কিভাবে OR-Tools ব্যবহার করে একটি ন্যাপস্যাক সমস্যা সমাধান করা যায়।

উদাহরণ

এখানে একটি ন্যাপস্যাক সমস্যার একটি গ্রাফিকাল চিত্রণ রয়েছে:

উপরের অ্যানিমেশনে, 50 আইটেম একটি বিনে প্যাক করা হয়। প্রতিটি আইটেমের একটি মান রয়েছে (আইটেমের সংখ্যা) এবং একটি ওজন (আইটেমের ক্ষেত্রফলের সাথে প্রায় সমানুপাতিক)। বিনটির ধারণক্ষমতা 850 বলে ঘোষণা করা হয়েছে এবং আমাদের লক্ষ্য হল এমন আইটেমগুলির সেট খুঁজে বের করা যা ধারণক্ষমতাকে অতিক্রম না করেই মোট মানকে সর্বাধিক করবে।

নিম্নলিখিত বিভাগগুলি এমন প্রোগ্রামগুলি বর্ণনা করে যা একটি ন্যাপস্যাক সমস্যার সমাধান করে। সম্পূর্ণ প্রোগ্রামের জন্য, সম্পূর্ণ প্রোগ্রাম দেখুন।

লাইব্রেরি আমদানি করুন

নিম্নলিখিত কোড প্রয়োজনীয় লাইব্রেরি আমদানি করে।

পাইথন

from ortools.algorithms.python import knapsack_solver

সি++

#include <algorithm>
#include <cstdint>
#include <iterator>
#include <numeric>
#include <sstream>
#include <vector>

#include "ortools/algorithms/knapsack_solver.h"

জাভা

import com.google.ortools.Loader;
import com.google.ortools.algorithms.KnapsackSolver;
import java.util.ArrayList;

সি#

using System;
using Google.OrTools.Algorithms;

ডেটা তৈরি করুন

নীচের কোডটি সমস্যার জন্য ডেটা তৈরি করে।

পাইথন

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]

সি++

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};

জাভা

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};

সি#

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 : একটি ভেক্টর যার মাত্র একটি এন্ট্রি, ন্যাপস্যাকের ক্ষমতা।

সমাধানকারী ঘোষণা করুন

নিম্নলিখিত কোডটি ন্যাপস্যাক সমাধানকারীকে ঘোষণা করে, যা ন্যাপস্যাক সমস্যার জন্য একটি বিশেষ সমাধানকারী।

পাইথন

solver = knapsack_solver.KnapsackSolver(
    knapsack_solver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
    "KnapsackExample",
)

সি++

KnapsackSolver solver(
    KnapsackSolver::KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
    "KnapsackExample");

জাভা

KnapsackSolver solver = new KnapsackSolver(
    KnapsackSolver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, "test");

সি#

KnapsackSolver solver = new KnapsackSolver(
    KnapsackSolver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, "KnapsackExample");

KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER বিকল্পটি সমাধানকারীকে সমস্যা সমাধানের জন্য শাখা এবং আবদ্ধ অ্যালগরিদম ব্যবহার করতে বলে।

দ্রষ্টব্য: CP-SAT সমাধানকারীর মতো, ন্যাপস্যাক সমাধানকারী পূর্ণসংখ্যার উপর কাজ করে, তাই প্রোগ্রামের ডেটাতে শুধুমাত্র পূর্ণসংখ্যা থাকতে পারে। যদি আপনার সমস্যায় অ-পূর্ণসংখ্যার মান থাকে, আপনি প্রথমে একটি যথেষ্ট বড় পূর্ণসংখ্যা দ্বারা ডেটা গুণ করে সেগুলিকে পূর্ণসংখ্যাতে রূপান্তর করতে পারেন। এখানে একটি অ-পূর্ণসংখ্যা সীমাবদ্ধতা রূপান্তর করার একটি উদাহরণ

সমাধানকারীকে কল করুন

নিম্নলিখিত কোডটি সমাধানকারীকে কল করে এবং সমাধানটি প্রিন্ট করে।

পাইথন

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)

সি++

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() << "}";

জাভা

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);

সি#

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)` আইটেম xটি সমাধানে অন্তর্ভুক্ত থাকলে `TRUE` প্রদান করে, `packed_items` হল সর্বোত্তম প্যাক করা আইটেমগুলির একটি তালিকা। একইভাবে, 'প্যাকড_ওয়েট' হল প্যাক করা আইটেমের ওজন। ### প্রোগ্রামের আউটপুট এখানে প্রোগ্রামের আউটপুট।

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]

সম্পূর্ণ প্রোগ্রাম

নীচে সম্পূর্ণ প্রোগ্রামগুলি রয়েছে যা ন্যাপস্যাক সমস্যার সমাধান করে।

পাইথন

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()

সি++

#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;
}

জাভা

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();
  }
}

সি#

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);
    }
}