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

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

## 本文概述

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

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

## 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``

``````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)。
由于没有额外的数据结构用于存储值。

• 在给定的列中填写" wi"。
• 不要在给定的栏中填写" 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"的二维数组。

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