本文概述

• C ++
• C
• Java
• python
• C#
• 的PHP
• C
• Java
• python
• C#
• 的PHP
• C ++
• Python3

给定n个物料的权重和值, 将这些物料放在容量为W的背包中, 以在背包中获得最大的总价值。换句话说, 给定两个整数数组val [0..n-1]和wt [0..n-1], 它们分别表示与n个项目关联的值和权重。还要给定代表背包容量的整数W, 找出val []的最大值子集, 以使该子集的权重之和小于或等于W。你不能破坏任何项目, 请选择完整的项目或不要不要选择它(0-1个属性)。

文章图片
方法1:通过暴力算法递归或穷举搜索。
方法:一个简单的解决方案是考虑项目的所有子集，并计算所有子集的总权重和值。只考虑总权值小于w的子集，从所有这些子集中选取最大值子集。
最优子结构:考虑所有项目的子集，每个项目可以有两种情况。

1. 情况1：该项目包括在最佳子集中。
2. 情况2：该项目不包括在最佳组合中。

因此, 可以从" n"项获得的最大值是以下两个值中的最大值。

1. 通过n-1个项和W权重(不包括第n个项)获得的最大值。
2. 第n个项目的值加上n-1个项目获得的最大值, W减去第n个项目(包括第n个项目)的权重。

【如何解决0-1背包问题（| DP-10（动态规划））】如果"第n个"项目的权重大于" W", 则第n个项目不能包含在内, 并且情况1是唯一的可能性。
下面是上述方法的实现：
C ++

/* A Naive recursive implementation of 0-1 Knapsack problem */ #include < bits/stdc++.h> using namespace std; // A utility function that returns // maximum of two integers int max( int a, int b) { return (a > b) ? a : b; } // Returns the maximum value that // can be put in a knapsack of capacity W int knapSack( int W, int wt[], int val[], int n) { // Base Case if (n == 0 || W == 0) return 0; // 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)); } // Driver code int main() { int val[] = { 60, 100, 120 }; int wt[] = { 10, 20, 30 }; int W = 50; int n = sizeof (val) / sizeof (val[0]); cout < < knapSack(W, wt, val, n); return 0; } // This code is contributed by rathbhupendra

C

/* A Naive recursive implementation of 0-1 Knapsack problem */ #include < stdio.h> // A utility function that returns // maximum of two integers int max( int a, int b) { return (a > b) ? a : b; } // Returns the maximum value that can be // put in a knapsack of capacity W int knapSack( int W, int wt[], int val[], int n) { // Base Case if (n == 0 || W == 0) return 0; // 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)); } // Driver program to test above function int main() { int val[] = { 60, 100, 120 }; int wt[] = { 10, 20, 30 }; int W = 50; int n = sizeof (val) / sizeof (val[0]); printf ( "%d" , knapSack(W, wt, val, n)); return 0; }

Java

/* A Naive recursive implementation of 0-1 Knapsack problem */ class Knapsack { // A utility function that returns // maximum of two integers static int max( int a, int b) { return (a > b) ? a : b; } // Returns the maximum value that // can be put in a knapsack of // capacity W static int knapSack( int W, int wt[], int val[], int n) { // Base Case if (n == 0 || W == 0 ) return 0 ; // 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 )); } // Driver code public static void main(String args[]) { int val[] = new int [] { 60 , 100 , 120 }; int wt[] = new int [] { 10 , 20 , 30 }; int W = 50 ; int n = val.length; System.out.println(knapSack(W, wt, val, n)); } } /*This code is contributed by Rajat Mishra */

python

# A naive recursive implementation # of 0-1 Knapsack Problem # Returns the maximum value that # can be put in a knapsack of # capacity W def knapSack(W, wt, val, n): # Base Case if n = = 0 or W = = 0 : return 0 # If weight of the nth item is # more than Knapsack of 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 )) # end of function knapSack #Driver Code val = [ 60 , 100 , 120 ] wt = [ 10 , 20 , 30 ] W = 50 n = len (val) print knapSack(W, wt, val, n) # This code is contributed by Nikhil Kumar Singh

C#

/* A Naive recursive implementation of 0-1 Knapsack problem */ using System; class GFG { // A utility function that returns // maximum of two integers static int max( int a, int b) { return (a > b) ? a : b; } // Returns the maximum value that can // be put in a knapsack of capacity W static int knapSack( int W, int [] wt, int [] val, int n) { // Base Case if (n == 0 || W == 0) return 0; // 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)); } // Driver code public static void Main() { int [] val = new int [] { 60, 100, 120 }; int [] wt = new int [] { 10, 20, 30 }; int W = 50; int n = val.Length; Console.WriteLine(knapSack(W, wt, val, n)); } } // This code is contributed by Sam007

的PHP

< ?php // A Naive recursive implementation // of 0-1 Knapsack problem // Returns the maximum value that // can be put in a knapsack of // capacity W function knapSack( $W , $wt , $val , $n ) { // Base Case if ( $n == 0 || $W == 0) return 0; // 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)); } // Driver Code $val = array (60, 100, 120); $wt = array (10, 20, 30); $W = 50; $n = count ( $val ); echo knapSack( $W , $wt , $val , $n ); // This code is contributed by Sam007 ?>

输出如下

220

应当注意, 上述函数一次又一次地计算相同的子问题。参见下面的递归树, K(1, 1)被评估两次。此幼稚递归解决方案的时间复杂度是指数(2 ^ n)。

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(n, W) K(3, 2) /\ /\ 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.

复杂度分析： 

• 时间复杂度：O(2^n)。
  由于存在多余的子问题。
• 辅助空间：O(1)。
  由于没有额外的数据结构用于存储值。

由于子问题再次计算，这个问题具有重叠子问题属性。所以0-1背包问题具有动态规划问题的两个性质(看这个和这个)。
方法2:与其他典型的动态规划(DP)问题一样，通过自底向上构造临时数组K[][]，可以避免重复计算相同的子问题。下面是基于动态编程的实现。
方法：在动态编程中, 我们将考虑与递归方法中提到的相同情况。在DP [] []表中, 将所有可能的权重(从" 1"到" W")视为列, 并将权重保留为行。
考虑到从" 1"到" i"的所有值, 状态DP [i] [j]将表示" j-weight"的最大值。因此, 如果我们考虑使用" wi"(" ith"行中的权重), 则可以将其填写在所有具有" weight values> wi"的列中。现在可以发生两种可能性：

• 在给定的列中填写" wi"。
• 不要在给定的栏中填写" wi"。

现在, 我们必须最大程度地考虑这两种可能性, 形式上, 如果我们不在" jth"列中填充" ith"权重, 则DP [i] [j]状态将与DP [i-1] [j]相同, 但是如果我们填充权重, 则DP [i] [j]将等于" wi"的值+上一行中权重为" j-wi"的列的值。因此, 我们将这两种可能性中的最大值用于填充当前状态。这种可视化将使概念更清晰：

Let weight elements = {1, 2, 3} Let weight values = {10, 15, 40} Capacity=6012345600000000101010101010102010152525252530 Explanation: For filling 'weight = 2' we come across 'j = 3' in which we take maximum of (10, 15 + DP[1][3-2]) = 25 || '2''2 filled' not filled012345600000000101010101010102010152525252530101540505565Explanation: For filling 'weight=3', we come across 'j=4' in which we take maximum of (25, 40 + DP[2][4-3]) = 50For filling 'weight=3' we come across 'j=5' in which we take maximum of (25, 40 + DP[2][5-3]) = 55For filling 'weight=3' we come across 'j=6' in which we take maximum of (25, 40 + DP[2][6-3]) = 65

C

// A Dynamic Programming based // solution for 0-1 Knapsack problem #include < stdio.h> // A utility function that returns // maximum of two integers int max( int a, int b) { return (a > b) ? a : b; } // Returns the maximum value that // can be put in a knapsack of capacity W int knapSack( int W, int wt[], int val[], int n) { int i, w; int K[n + 1][W + 1]; // Build table K[][] in bottom up manner for (i = 0; i < = n; i++) { for (w = 0; w < = W; w++) { if (i == 0 || w == 0) K[i][w] = 0; else if (wt[i - 1] < = w) K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]); else K[i][w] = K[i - 1][w]; } } return K[n][W]; } // Driver Code int main() { int val[] = { 60, 100, 120 }; int wt[] = { 10, 20, 30 }; int W = 50; int n = sizeof (val) / sizeof (val[0]); printf ( "%d" , knapSack(W, wt, val, n)); return 0; }

Java

// A Dynamic Programming based solution // for 0-1 Knapsack problem class Knapsack { // A utility function that returns // maximum of two integers static int max( int a, int b) { return (a > b) ? a : b; } // Returns the maximum value that can // be put in a knapsack of capacity W static int knapSack( int W, int wt[], int val[], int n) { int i, w; int K[][] = new int [n + 1 ][W + 1 ]; // Build table K[][] in bottom up manner for (i = 0 ; i < = n; i++) { for (w = 0 ; w < = W; w++) { if (i == 0 || w == 0 ) K[i][w] = 0 ; else if (wt[i - 1 ] < = w) K[i][w] = max(val[i - 1 ] + K[i - 1 ][w - wt[i - 1 ]], K[i - 1 ][w]); else K[i][w] = K[i - 1 ][w]; } } return K[n][W]; } // Driver code public static void main(String args[]) { int val[] = new int [] { 60 , 100 , 120 }; int wt[] = new int [] { 10 , 20 , 30 }; int W = 50 ; int n = val.length; System.out.println(knapSack(W, wt, val, n)); } } /*This code is contributed by Rajat Mishra */

python

# A Dynamic Programming based Python # Program for 0-1 Knapsack problem # Returns the maximum value that can # be put in a knapsack of capacity W def knapSack(W, wt, val, n): K = [[ 0 for x in range (W + 1 )] for x in range (n + 1 )] # Build table K[][] in bottom up manner for i in range (n + 1 ): for w in range (W + 1 ): if i = = 0 or w = = 0 : K[i][w] = 0 elif wt[i - 1 ] < = w: K[i][w] = max (val[i - 1 ] + K[i - 1 ][w - wt[i - 1 ]], K[i - 1 ][w]) else : K[i][w] = K[i - 1 ][w] return K[n][W] # Driver code val = [ 60 , 100 , 120 ] wt = [ 10 , 20 , 30 ] W = 50 n = len (val) print (knapSack(W, wt, val, n)) # This code is contributed by Bhavya Jain

C#

// A Dynamic Programming based solution for // 0-1 Knapsack problem using System; class GFG { // A utility function that returns // maximum of two integers static int max( int a, int b) { return (a > b) ? a : b; } // Returns the maximum value that // can be put in a knapsack of // capacity W static int knapSack( int W, int [] wt, int [] val, int n) { int i, w; int [, ] K = new int [n + 1, W + 1]; // Build table K[][] in bottom // up manner for (i = 0; i < = n; i++) { for (w = 0; w < = W; w++) { if (i == 0 || w == 0) K[i, w] = 0; else if (wt[i - 1] < = w) K[i, w] = Math.Max( val[i - 1] + K[i - 1, w - wt[i - 1]], K[i - 1, w]); else K[i, w] = K[i - 1, w]; } } return K[n, W]; } // Driver code static void Main() { int [] val = new int [] { 60, 100, 120 }; int [] wt = new int [] { 10, 20, 30 }; int W = 50; int n = val.Length; Console.WriteLine(knapSack(W, wt, val, n)); } } // This code is contributed by Sam007

的PHP

< ?php // A Dynamic Programming based solution // for 0-1 Knapsack problem // Returns the maximum value that // can be put in a knapsack of // capacity W function knapSack( $W , $wt , $val , $n ) {$K = array ( array ()); // Build table K[][] in // bottom up manner for ( $i = 0; $i < = $n ; $i ++) { for ( $w = 0; $w < = $W ; $w ++) { if ( $i == 0 || $w == 0) $K [ $i ][ $w ] = 0; else if ( $wt [ $i - 1] < = $w ) $K [ $i ][ $w ] = max( $val [ $i - 1] + $K [ $i - 1][ $w - $wt [ $i - 1]], $K [ $i - 1][ $w ]); else $K [ $i ][ $w ] = $K [ $i - 1][ $w ]; } }return $K [ $n ][ $W ]; } // Driver Code $val = array (60, 100, 120); $wt = array (10, 20, 30); $W = 50; $n = count ( $val ); echo knapSack( $W , $wt , $val , $n ); // This code is contributed by Sam007. ?>

输出如下

220

复杂度分析： 

• 时间复杂度：O(N * W)。
  其中" N"是重量元素的数量, " W"是容量。对于每个重量元素, 我们遍历所有重量容量1 < = w < = W。
• 辅助空间：O(N * W)。
  使用大小为" N * W"的二维数组。

方法3:此方法使用内存技术(递归方法的扩展)。
此方法基本上是递归方法的扩展, 因此我们可以克服计算冗余案例的问题, 从而增加了复杂性。我们可以通过简单地创建一个二维数组来解决这个问题, 如果我们第一次得到它, 它可以存储一个特定的状态(n, w)。现在, 如果我们再次遇到相同的状态(n, w), 而不是以指数复杂度进行计算, 我们可以直接以固定时间返回存储在表中的结果。在此方面, 此方法相对于递归方法具有优势。
C ++

// Here is the top-down approach of // dynamic programming #include < bits/stdc++.h> using namespace std; // Returns the value of maximum profit int knapSackRec( int W, int wt[], int val[], int i, int ** dp) { // base condition if (i < 0) return 0; if (dp[i][W] != -1) return dp[i][W]; if (wt[i] > W) { // Store the value of function call // stack in table before return dp[i][W] = knapSackRec(W, wt, val, i - 1, dp); return dp[i][W]; } else { // Store value in a table before return dp[i][W] = max(val[i] + knapSackRec(W - wt[i], wt, val, i - 1, dp), knapSackRec(W, wt, val, i - 1, dp)); // Return value of table after storing return dp[i][W]; } } int knapSack( int W, int wt[], int val[], int n) { // double pointer to declare the // table dynamically int ** dp; dp = new int *[n]; // loop to create the table dynamically for ( int i = 0; i < n; i++) dp[i] = new int [W + 1]; // loop to initially filled the // table with -1 for ( int i = 0; i < n; i++) for ( int j = 0; j < W + 1; j++) dp[i][j] = -1; return knapSackRec(W, wt, val, n - 1, dp); } // Driver Code int main() { int val[] = { 10, 20, 30 }; int wt[] = { 1, 1, 1 }; int W = 2; int n = sizeof (val) / sizeof (val[0]); cout < < knapSack(W, wt, val, n); return 0; }

Python3

# This is the memoization approach of # 0 / 1 Knapsack in Python in simple # we can say recursion + memoization = DP # driver code val = [ 60 , 100 , 120 ] wt = [ 10 , 20 , 30 ] W = 50 n = len (val) # We initialize the matrix with -1 at first. t = [[ - 1 for i in range (W + 1 )] for j in range (n + 1 )] def knapsack(wt, val, W, n): # base conditions if n = = 0 or W = = 0 : return 0 if t[n][W] ! = - 1 : return t[n][W] # choice diagram code if wt[n - 1 ] < = W: t[n][W] = max ( val[n - 1 ] + knapsack( wt, val, W - wt[n - 1 ], n - 1 ), knapsack(wt, val, W, n - 1 )) return t[n][W] elif wt[n - 1 ] > W: t[n][W] = knapsack(wt, val, W, n - 1 ) return t[n][W] print (knapsack(wt, val, W, n)) # This code is contributed by Prosun Kumar Sarkar

输出如下

50

复杂度分析： 

• 时间复杂度：O(N * W)。
  由于避免了状态的冗余计算。
• 辅助空间：O(N * W)。
  使用2D数组数据结构存储中间状态-：

[注意：对于32位整数, 请使用long而不是int。]
参考文献：

• http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf
• http://www.cse.unl.edu/~goddard/Courses/CSCE310J/Lectures/Lecture8-Dynamilsbin.pdf

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

推荐阅读

• 

  佳能750d可以换什么样的镜头
• 

  面料涤纶里料棉纶的衣服怎么洗 面料涤纶里料棉纶的衣服如何洗
• 

  快赔和保险有什么区别
• 

  mole|预算不超过2000元，要有5g、不卡，朋友们能否给点建议？
• 

  崇德老人八字例解（六）
• 

  痛风后果严重吗
• 

  stm32逻辑分析porta
• 

  秋葵焯水要切开不
• 

  万能看图王怎么卸载？万能看图王卸载方法
• 

  含有近义词的词语 含有近义词的词语 四字
• 

  利用手机QQ无限刷手机上网流量 三网通用
• 

  新冠疫苗接种后的注意事项 打新冠疫苗可以吃生鱼片吗
• 

  戒烟的过程中有点心慌是什么情况，要怎么办啊？
• 

  得了艾滋病应该怎么办 如果患上艾滋病怎么办
• 

  夏天如何培养天竺葵盆栽 夏天如何培养天竺葵，夏天如何培养天竺葵苗
• 

  wi-fi|联想发布 Yoga 7i 翻转本：可选 14/16 英寸屏
• 

  分享一下你们最喜欢的微信头像？
• 

  《雪鹰领主》进入薪火宫的条件 雪鹰领主招募
• 

  虚拟主机如何搭建shopex，虚拟主机如何搭建传奇游戏
• 

  考研申请书

• 算法题（如何实现求和树（））
• C/C++棘手程序集锦和详细介绍
• 6秘技让xp系统迅速完成开关机
• 伪IE图标删除?高手简单搞定
• 高手教你辨别ARP欺骗原理及防范被骗
• 简单几招处理局域网不能互相访问故障
• 玩转XP上网无忧?3款软件容易搞定
• 盘点windows下那些鲜为人知的ftp命令
• 知道黑客技能 揭开神秘黑客面纱