如何解决0-1背包问题？| DP-10（动态规划）

2021年3月21日16:58:07 发表评论 1,044 次浏览

本文概述

给定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个项目)的权重。

如果"第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=6

0   1   2   3   4   5   6

0  0   0   0   0   0   0   0

1  0  10  10  10  10  10  10

2  0  10  15  25  25  25  25

3  0
 
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 filled  

0   1   2   3   4   5   6

0  0   0   0   0   0   0   0

1  0  10  10  10  10  10  10

2  0  10  15  25  25  25  25

3  0  10  15  40  50  55  65

Explanation:
For filling 'weight=3', we come across 'j=4' in which 
we take maximum of (25, 40 + DP[2][4-3]) 
= 50

For filling 'weight=3' 
we come across 'j=5' in which 
we take maximum of (25, 40 + DP[2][5-3])
= 55

For 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

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

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: