حل مساله کوله پشتی (Knapsack Problem) — به زبان ساده

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

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

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

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?>

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

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 

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?>