Vấn đề về Knapsack

Trong bài toán về ba lô, bạn cần đóng gói một tập hợp các món đồ với các giá trị cho trước và kích thước (chẳng hạn như trọng lượng hoặc thể tích) vào thùng chứa có dung tích tối đa của Google. Nếu tổng kích thước của các mặt hàng vượt quá hạn mức, bạn không thể đóng gói tất cả các mặt hàng. Trong trường hợp đó, vấn đề là phải chọn một tập hợp con các mục có tổng giá trị tối đa phù hợp với vùng chứa.

Các phần sau đây trình bày cách giải bài toán ba lô bằng OR-Tools.

Ví dụ:

Dưới đây là mô tả dạng hình ảnh về một vấn đề về ba lô:

Trong ảnh động ở trên, các mục 50 được đóng gói vào một thùng. Mỗi mục đều có một giá trị (số lượng trên mặt hàng) và trọng lượng (tỷ lệ gần đúng với diện tích của mặt hàng) mục). Thùng được khai báo có dung lượng là 850 và mục tiêu của chúng ta là tìm tập hợp giúp tối đa hoá tổng giá trị mà không vượt quá hạn mức.

Các phần sau đây mô tả các chương trình giải quyết vấn đề về ba lô. Để xem các chương trình đầy đủ, hãy xem phần Hoàn thành chương trình.

Nhập thư viện

Mã sau đây nhập các thư viện bắt buộc.

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;

Tạo dữ liệu

Mã dưới đây sẽ tạo dữ liệu cho sự cố này.

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

Dữ liệu này bao gồm:

• weights: Vectơ chứa trọng số của các mục.
• values: Vectơ chứa giá trị của các mục.
• capacities: Một vectơ chỉ có một phần tử, sức chứa của chiếc ba lô.

Khai báo trình giải

Mã sau đây khai báo trình giải ba lô, một công cụ giải chuyên biệt cho bài tập ba lô.

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

Lựa chọn KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER đưa ra cho người giải sử dụng thuật toán nhánh và ràng buộc để giải bài toán này.

Lưu ý: Giống như trình giải CP-SAT, trình giải ba lô làm việc trên các số nguyên, vì vậy dữ liệu trong chương trình chỉ có thể chứa số nguyên. Nếu sự cố của bạn có chứa giá trị không phải là số nguyên, thì trước tiên bạn có thể chuyển đổi các giá trị đó thành số nguyên bằng cách nhân bằng một số nguyên đủ lớn. Sau đây là một ví dụ về cách chuyển đổi một quy tắc ràng buộc không phải số nguyên

Gọi trình giải

Đoạn mã sau đây gọi trình giải và in đáp án.

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

Trước tiên, chương trình khởi chạy trình giải rồi gọi nó bằng computed_value = solver.Solve(). Tổng giá trị của nghiệm tối ưu là computed_value, bằng nhau là tổng trọng số trong trường hợp này. Sau đó, chương trình nhận các chỉ mục của trong dung dịch như sau:

packed_items = [x for x in range(0, len(weights[0]))
                  if solver.BestSolutionContains(x)]

Vì "solver.BestSolutioncó(x)" trả về "TRUE" nếu có mục x trong giải pháp, "packed_items" là danh sách các mặt hàng được đóng gói tối ưu. Tương tự, "packed_weights" là trọng lượng của các mặt hàng được đóng gói. ### Kết quả của chương trình Đây là kết quả của chương trình.

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]

Hoàn tất chương trình

Dưới đây là các chương trình hoàn chỉnh giải quyết vấn đề về ba lô.

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