ในปัญหาเกี่ยวกับกระเป๋าเป้ คุณต้องบรรจุชุดสินค้าซึ่งมีค่าและขนาดที่ระบุ (เช่น น้ําหนักหรือวอลุ่ม) ในคอนเทนเนอร์ที่มีความจุสูงสุด หากขนาดสินค้าทั้งหมดเกินขีดจํากัด คุณจะแพ็กสินค้าทั้งหมดไม่ได้ ในกรณีดังกล่าว ปัญหาคือการเลือกชุดย่อยของค่าสูงสุด ที่จะพอดีกับคอนเทนเนอร์
ส่วนต่อไปนี้จะแสดงวิธีแก้ไขปัญหาเกี่ยวกับ Knopack โดยใช้เครื่องมือ OR
ตัวอย่าง
ภาพกราฟิกของปัญหา Knpack มีดังนี้
ในภาพเคลื่อนไหวข้างต้น สินค้า 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
: เวกเตอร์ที่มีเพียงข้อมูลเดียวคือความจุของ Knopack
ประกาศเครื่องมือแก้โจทย์
โค้ดต่อไปนี้จะประกาศเครื่องมือแก้โจทย์คณิตซึ่งมีไว้สําหรับแก้โจทย์พิเศษ
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
จะแจ้งให้เครื่องมือแก้โจทย์คณิตใช้อัลกอริทึม Branch and bound เพื่อแก้ปัญหา
โทรหาเครื่องมือแก้โจทย์
โค้ดต่อไปนี้จะเรียกเครื่องมือแก้โจทย์และพิมพ์โซลูชัน
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.BestSolutionContains(x)` แสดงผล `TRUE` หากรายการ x รวมอยู่ในโซลูชัน `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]
สิ้นสุดโปรแกรม
ด้านล่างนี้คือโปรแกรมที่สมบูรณ์ซึ่งช่วยแก้ปัญหาเกี่ยวกับ Knapack
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); } }