حل مساله کوله پشتی (Knapsack Problem) – به زبان ساده
در این مطلب، روش حل مساله کوله پشتی (Knapsack Problem) بیان و پیادهسازی آن در زبانهای برنامهنویسی گوناگون شامل «سیپلاسپلاس» ++C، «جاوا» (Java)، «پایتون» (Python)، «سیشارپ» (#C) و «پیاچپی» (PHP) انجام شده است. وزن و ارزش n شی داده شده است.
حل مساله کوله پشتی
هدف، قرار دادن این اشیا در کولهپشتی با ظرفیت W به صورتی است که مقدار ارزش بیشینه حاصل شود. به بیان دیگر، دو آرایه صحیح [val[0..n-1 و [wt[0..n-1 وجود دارند که به ترتیب نشانگر مقادیر و وزنهای تخصیص داده شده به n عنصر هستند. همچنین، یک عدد صحیح W نیز داده شده است که ظرفیت کوله پشتی را نشان میدهد.
هدف، پیدا کردن زیرمجموعهای با مقدار بیشینه []val است که در آن، مجموع وزنها کوچکتر یا مساوی W باشد. امکان خورد کردن اشیا وجود ندارد و باید یک شی را به طور کامل انتخاب کرد و یا اصلا انتخاب نکرد. این گونه از مساله کوله پشتی را، «مساله کوله پشتی ۱-۰» میگویند.
یک راهکار ساده برای حل این مساله، در نظر گرفتن همه زیر مجموعههای ممکن از اشیا و محاسبه وزن و ارزش کلی هر یک از آنها است. سپس، از میان همه زیرمجموعهها مواردی انتخاب میشوند که وزن کلی آنها کمتر یا مساوی W باشد. در نهایت، از میان زیرمجموعههای دارای وزن کمتر یا مساوی W، زیرمجموعهای با ارزش بیشینه انتخاب میشود.
۱. زیر ساختار بهینه
برای در نظر گرفتن همه عناصر، دو حالت برای هر عنصر وجود دارد. در حالت اول، عنصر در زیر مجموعه بهینه قرار میگیرد و در حالت دوم، عنصر در زیر مجموعه بهینه قرار نمیگیرد. بنابراین، ارزش بیشینهای که میتوان از n عنصر به دست آورد، برابر با بیشینه دو ارزش زیر است:
- ارزش بیشینه حاصل شده از n-1 عنصر و وزن W (به استثنای عنصر nاُم)
- ارزش عنصر nاُم بهعلاوه ارزش بیشینه به دست آمده از n-1 عنصر و وزن W منهای وزن عنصر nاُم
اگر وزن عنصر nاُم بزرگتر از W باشد، این عنصر نمیتواند در کوله پشتی قرار بگیرد و تنها حالت ۱ امکانپذیر است.
۲. زیرمسالههای همپوشان
در ادامه، روش پیادهسازی بازگشتی ساختار بازگشتی بیان شده در بالا ارائه شده است.
حل مساله کوله پشتی ۱-۰ در ++C
1/* A Naive recursive implementation of 0-1 Knapsack problem */
2#include <bits/stdc++.h>
3using namespace std;
4
5// A utility function that returns maximum of two integers
6int max(int a, int b) { return (a > b)? a : b; }
7
8// Returns the maximum value that
9// can be put in a knapsack of capacity W
10int knapSack(int W, int wt[], int val[], int n)
11{
12
13// Base Case
14if (n == 0 || W == 0)
15 return 0;
16
17// If weight of the nth item is more
18// than Knapsack capacity W, then
19// this item cannot be included
20// in the optimal solution
21if (wt[n-1] > W)
22 return knapSack(W, wt, val, n-1);
23
24// Return the maximum of two cases:
25// (1) nth item included
26// (2) not included
27else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
28 knapSack(W, wt, val, n-1) );
29}
30
31// Driver code
32int main()
33{
34 int val[] = {60, 100, 120};
35 int wt[] = {10, 20, 30};
36 int W = 50;
37 int n = sizeof(val)/sizeof(val[0]);
38 cout<<knapSack(W, wt, val, n);
39 return 0;
40}
41
42// This code is contributed by rathbhupendra
حل مساله کوله پشتی ۱-۰ در C
1/* A Naive recursive implementation of 0-1 Knapsack problem */
2#include<stdio.h>
3
4// A utility function that returns maximum of two integers
5int max(int a, int b) { return (a > b)? a : b; }
6
7// Returns the maximum value that can be put in a knapsack of capacity W
8int knapSack(int W, int wt[], int val[], int n)
9{
10 // Base Case
11 if (n == 0 || W == 0)
12 return 0;
13
14 // If weight of the nth item is more than Knapsack capacity W, then
15 // this item cannot be included in the optimal solution
16 if (wt[n-1] > W)
17 return knapSack(W, wt, val, n-1);
18
19 // Return the maximum of two cases:
20 // (1) nth item included
21 // (2) not included
22 else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
23 knapSack(W, wt, val, n-1)
24 );
25}
26
27// Driver program to test above function
28int main()
29{
30 int val[] = {60, 100, 120};
31 int wt[] = {10, 20, 30};
32 int W = 50;
33 int n = sizeof(val)/sizeof(val[0]);
34 printf("%d", knapSack(W, wt, val, n));
35 return 0;
36}
حل مساله کوله پشتی ۱-۰ در جاوا
1/* A Naive recursive implementation of 0-1 Knapsack problem */
2class Knapsack
3{
4
5 // A utility function that returns maximum of two integers
6 static int max(int a, int b) { return (a > b)? a : b; }
7
8 // Returns the maximum value that can be put in a knapsack of capacity W
9 static int knapSack(int W, int wt[], int val[], int n)
10 {
11 // Base Case
12 if (n == 0 || W == 0)
13 return 0;
14
15 // If weight of the nth item is more than Knapsack capacity W, then
16 // this item cannot be included in the optimal solution
17 if (wt[n-1] > W)
18 return knapSack(W, wt, val, n-1);
19
20 // Return the maximum of two cases:
21 // (1) nth item included
22 // (2) not included
23 else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
24 knapSack(W, wt, val, n-1)
25 );
26 }
27
28
29 // Driver program to test above function
30 public static void main(String args[])
31 {
32 int val[] = new int[]{60, 100, 120};
33 int wt[] = new int[]{10, 20, 30};
34 int W = 50;
35 int n = val.length;
36 System.out.println(knapSack(W, wt, val, n));
37 }
38}
39/*This code is contributed by Rajat Mishra */
حل مساله کوله پشتی ۱-۰ در پایتون
1#A naive recursive implementation of 0-1 Knapsack Problem
2
3# Returns the maximum value that can be put in a knapsack of
4# capacity W
5def knapSack(W , wt , val , n):
6
7 # Base Case
8 if n == 0 or W == 0 :
9 return 0
10
11 # If weight of the nth item is more than Knapsack of capacity
12 # W, then this item cannot be included in the optimal solution
13 if (wt[n-1] > W):
14 return knapSack(W , wt , val , n-1)
15
16 # return the maximum of two cases:
17 # (1) nth item included
18 # (2) not included
19 else:
20 return max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1),
21 knapSack(W , wt , val , n-1))
22
23# end of function knapSack
24
25# To test above function
26val = [60, 100, 120]
27wt = [10, 20, 30]
28W = 50
29n = len(val)
30print knapSack(W , wt , val , n)
31
32# This code is contributed by Nikhil Kumar Singh
حل مساله کوله پشتی ۱-۰ در #C
1/* A Naive recursive implementation of
20-1 Knapsack problem */
3using System;
4
5class GFG {
6
7 // A utility function that returns
8 // maximum of two integers
9 static int max(int a, int b)
10 {
11 return (a > b)? a : b;
12 }
13
14 // Returns the maximum value that can
15 // be put in a knapsack of capacity W
16 static int knapSack(int W, int []wt,
17 int []val, int n)
18 {
19
20 // Base Case
21 if (n == 0 || W == 0)
22 return 0;
23
24 // If weight of the nth item is
25 // more than Knapsack capacity W,
26 // then this item cannot be
27 // included in the optimal solution
28 if (wt[n-1] > W)
29 return knapSack(W, wt, val, n-1);
30
31 // Return the maximum of two cases:
32 // (1) nth item included
33 // (2) not included
34 else return max( val[n-1] +
35 knapSack(W-wt[n-1], wt, val, n-1),
36 knapSack(W, wt, val, n-1));
37 }
38
39 // Driver function
40 public static void Main()
41 {
42 int []val = new int[]{60, 100, 120};
43 int []wt = new int[]{10, 20, 30};
44 int W = 50;
45 int n = val.Length;
46
47 Console.WriteLine(knapSack(W, wt, val, n));
48 }
49}
50
51// This code is contributed by Sam007
حل مساله کوله پشتی ۱-۰ در PHP
1<?php
2// A Naive recursive implementation
3// of 0-1 Knapsack problem
4
5// Returns the maximum value that
6// can be put in a knapsack of
7// capacity W
8function knapSack($W, $wt, $val, $n)
9{
10 // Base Case
11 if ($n == 0 || $W == 0)
12 return 0;
13
14 // If weight of the nth item is
15 // more than Knapsack capacity
16 // W, then this item cannot be
17 // included in the optimal solution
18 if ($wt[$n - 1] > $W)
19 return knapSack($W, $wt, $val, $n - 1);
20
21 // Return the maximum of two cases:
22 // (1) nth item included
23 // (2) not included
24 else
25 return max($val[$n - 1] +
26 knapSack($W - $wt[$n - 1],
27 $wt, $val, $n - 1),
28 knapSack($W, $wt, $val, $n-1));
29}
30
31 // Driver Code
32 $val = array(60, 100, 120);
33 $wt = array(10, 20, 30);
34 $W = 50;
35 $n = count($val);
36 echo knapSack($W, $wt, $val, $n);
37
38// This code is contributed by Sam007
39?>
خروجی قطعه کدهای بالا به صورت زیر است.
220
حل مساله کوله پشتی با برنامهنویسی پویا
شایان ذکر است که تابع بالا، زیرمسالههای مشابه را بارها و بارها حل میکند. برای مثال، زیر درخت بازگشتی (K(1, 1 دو بار محاسبه میشود. پیچیدگی زمانی این روش بازگشتیِ ساده به صورت نمایی و از درجه (O(2n است.
In the following recursion tree, K() refers to knapSack(). The two parameters indicated in the following recursion tree are n and W. The recursion tree is for following sample inputs. wt[] = {1, 1, 1}, W = 2, val[] = {10, 20, 30} K(3, 2) ---------> K(n, W) / \ / \ K(2,2) K(2,1) / \ / \ / \ / \ K(1,2) K(1,1) K(1,1) K(1,0) / \ / \ / \ / \ / \ / \ K(0,2) K(0,1) K(0,1) K(0,0) K(0,1) K(0,0) Recursion tree for Knapsack capacity 2 units and 3 items of 1 unit weight.
با توجه به آنکه زیرمسالهها مجددا محاسبه میشوند، این مساله دارای خصوصیت زیرمسالههای همپوشان است. بنابراین، مساله کولهپشتی ۱-۰ دارای هر دو خصوصیت مسائل «برنامهنویسی پویا» (Dynamic Programming | DP) است. همچون دیگر مسائل برنامهنویسی پویا (DP)، میتوان از محاسبه مجدد زیرمسالههای مشابه با ساخت یک آرایه موقت [][]K به صورت پایین به بالا، اجتناب کرد. در ادامه، پیادهسازی راه حل این مساله با استفاده از برنامهنویسی پویا ارائه شده است.
حل مساله کوله پشتی ۱-۰ با برنامهنویسی پویا در ++C
1// A Dynamic Programming based solution for 0-1 Knapsack problem
2#include<stdio.h>
3
4// A utility function that returns maximum of two integers
5int max(int a, int b) { return (a > b)? a : b; }
6
7// Returns the maximum value that can be put in a knapsack of capacity W
8int knapSack(int W, int wt[], int val[], int n)
9{
10 int i, w;
11 int K[n+1][W+1];
12
13 // Build table K[][] in bottom up manner
14 for (i = 0; i <= n; i++)
15 {
16 for (w = 0; w <= W; w++)
17 {
18 if (i==0 || w==0)
19 K[i][w] = 0;
20 else if (wt[i-1] <= w)
21 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
22 else
23 K[i][w] = K[i-1][w];
24 }
25 }
26
27 return K[n][W];
28}
29
30int main()
31{
32 int val[] = {60, 100, 120};
33 int wt[] = {10, 20, 30};
34 int W = 50;
35 int n = sizeof(val)/sizeof(val[0]);
36 printf("%d", knapSack(W, wt, val, n));
37 return 0;
38}
حل مساله کوله پشتی ۱-۰ با برنامهنویسی پویا در جاوا
1// A Dynamic Programming based solution for 0-1 Knapsack problem
2class Knapsack
3{
4
5 // A utility function that returns maximum of two integers
6 static int max(int a, int b) { return (a > b)? a : b; }
7
8 // Returns the maximum value that can be put in a knapsack of capacity W
9 static int knapSack(int W, int wt[], int val[], int n)
10 {
11 int i, w;
12 int K[][] = new int[n+1][W+1];
13
14 // Build table K[][] in bottom up manner
15 for (i = 0; i <= n; i++)
16 {
17 for (w = 0; w <= W; w++)
18 {
19 if (i==0 || w==0)
20 K[i][w] = 0;
21 else if (wt[i-1] <= w)
22 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
23 else
24 K[i][w] = K[i-1][w];
25 }
26 }
27
28 return K[n][W];
29 }
30
31
32 // Driver program to test above function
33 public static void main(String args[])
34 {
35 int val[] = new int[]{60, 100, 120};
36 int wt[] = new int[]{10, 20, 30};
37 int W = 50;
38 int n = val.length;
39 System.out.println(knapSack(W, wt, val, n));
40 }
41}
42/*This code is contributed by Rajat Mishra */
حل مساله کوله پشتی ۱-۰ با برنامهنویسی پویا در پایتون
1# A Dynamic Programming based Python Program for 0-1 Knapsack problem
2# Returns the maximum value that can be put in a knapsack of capacity W
3def knapSack(W, wt, val, n):
4 K = [[0 for x in range(W+1)] for x in range(n+1)]
5
6 # Build table K[][] in bottom up manner
7 for i in range(n+1):
8 for w in range(W+1):
9 if i==0 or w==0:
10 K[i][w] = 0
11 elif wt[i-1] <= w:
12 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
13 else:
14 K[i][w] = K[i-1][w]
15
16 return K[n][W]
17
18# Driver program to test above function
19val = [60, 100, 120]
20wt = [10, 20, 30]
21W = 50
22n = len(val)
23print(knapSack(W, wt, val, n))
24
25# This code is contributed by Bhavya Jain
حل مساله کوله پشتی ۱-۰ با برنامه نویسی پویا در #C
1// A Dynamic Programming based solution for
2// 0-1 Knapsack problem
3using System;
4
5class GFG {
6
7 // A utility function that returns
8 // maximum of two integers
9 static int max(int a, int b)
10 {
11 return (a > b) ? a : b;
12 }
13
14 // Returns the maximum value that
15 // can be put in a knapsack of
16 // capacity W
17 static int knapSack(int W, int []wt,
18 int []val, int n)
19 {
20 int i, w;
21 int [,]K = new int[n+1,W+1];
22
23 // Build table K[][] in bottom
24 // up manner
25 for (i = 0; i <= n; i++)
26 {
27 for (w = 0; w <= W; w++)
28 {
29 if (i == 0 || w == 0)
30 K[i,w] = 0;
31 else if (wt[i-1] <= w)
32 K[i,w] = Math.Max(val[i-1]
33 + K[i-1,w-wt[i-1]],
34 K[i-1,w]);
35 else
36 K[i,w] = K[i-1,w];
37 }
38 }
39
40 return K[n,W];
41 }
42
43 // Driver code
44 static void Main()
45 {
46 int []val = new int[]{60, 100, 120};
47 int []wt = new int[]{10, 20, 30};
48 int W = 50;
49 int n = val.Length;
50
51 Console.WriteLine(
52 knapSack(W, wt, val, n));
53 }
54}
55
56// This code is contributed by Sam007
حل مساله کوله پشتی ۱-۰ با برنامه نویسی پویا در PHP
1<?php
2// A Dynamic Programming based solution
3// for 0-1 Knapsack problem
4
5// Returns the maximum value that
6// can be put in a knapsack of
7// capacity W
8function knapSack($W, $wt, $val, $n)
9{
10
11 $K = array(array());
12
13 // Build table K[][] in
14 // bottom up manner
15 for ($i = 0; $i <= $n; $i++)
16 {
17 for ($w = 0; $w <= $W; $w++)
18 {
19 if ($i == 0 || $w == 0)
20 $K[$i][$w] = 0;
21 else if ($wt[$i - 1] <= $w)
22 $K[$i][$w] = max($val[$i - 1] +
23 $K[$i - 1][$w -
24 $wt[$i - 1]],
25 $K[$i - 1][$w]);
26 else
27 $K[$i][$w] = $K[$i - 1][$w];
28 }
29 }
30
31 return $K[$n][$W];
32}
33
34 // Driver Code
35 $val = array(60, 100, 120);
36 $wt = array(10, 20, 30);
37 $W = 50;
38 $n = count($val);
39 echo knapSack($W, $wt, $val, $n);
40
41// This code is contributed by Sam007.
42?>
خروجی قطعه کدها بالا به صورت زیر است.
220
پیچیدگی زمانی روش بالا از درجه (O(nW است که در آن، n تعداد عناصر و W ظرفیت کولهپشتی است.
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای برنامه نویسی
- آموزش ساختمان دادهها
- مجموعه آموزشهای ساختمان داده و طراحی الگوریتم
- رنگآمیزی گراف به روش حریصانه — به زبان ساده
- الگوریتم دایجسترا (Dijkstra) — از صفر تا صد
- الگوریتم پریم — به زبان ساده
- حل مساله n وزیر با الگوریتم پسگرد (Backtracking) — به زبان ساده
^^
لطفا کد چاپ اقلام انتخابی توسط الگوریتم بعد از اجرا را هم بگذارید یا توضیح دهید.
با سلام. الگوریتم پایتون برای مساله کوله پشتی بسیار آموزنده بود. منتها میخواستم متغیر های تصمیم گیری برداشت اقلام را هم داشته باشم نه اینکه فقط به مقدار تابع هدف نهایی برسم. چکار باید انجام داد؟
“Code Javascript”
الگوریتم کوله پشتی
/ If weight of the nth item is more
// than Knapsack capacity W, then
// this item cannot be included
// in the optimal solution
if (wt[n-1] > W)
return knapSack(W, wt, val, n-1);
// Return the maximum of two cases:
// (1) nth item included
// (2) not included
else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
knapSack(W, wt, val, n-1) );
}
var val =new Array (60, 100, 120);
var wt =new Array( 10, 20, 30);
var W = 50;
var n =Math.floor(val.length/(val[0].toString().length));
console.log(knapSack(W, wt, val, n))