动态规划：0/1背包问题

01背包问题是一个经典的动态规划问题，它询问在给定的物品和背包容量下，如何选择物品使得背包中的物品总价值最大，同时保证不超过背包的容量限制。物品不能分割，每个物品只能选择放入或不放入背包。

问题定义

• 输入：

  • 物品个数 ( n )
  • 背包容量 ( W )
  • 每个物品的重量 ( w[i] )
  • 每个物品的价值 ( v[i] )

• 输出：

  • 背包所能装载的最大价值

动态规划解法思路

1. 定义状态：

   • 定义 ( dp[i][j] ) 为从前 ( i ) 个物品中选择，总重量不超过 ( j ) 时的最大价值。

2. 状态转移方程：

   • 如果不选择第 ( i ) 个物品，则 ( dp[i][j] = dp[i-1][j] )。
   • 如果选择第 ( i ) 个物品（前提是 ( j \geq w[i] )），则 ( dp[i][j] = dp[i-1][j-w[i]] + v[i] )。
   • 综合考虑上述两种情况，有：
     [
     dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) \quad \text{if } j \geq w[i]
     ]
   • 如果 ( j < w[i] )，则只能选择不拿 ( i ) 物品的情况：( dp[i][j] = dp[i-1][j] )。

3. 初始化条件：

   • ( dp[0][j] ) 为 0，因为没有物品时，最大价值为 0。
   • ( dp[i][0] ) 也为 0，因为容量为 0 时，不能装任何物品。

4. 计算顺序：

   • 从 ( i = 1 ) 到 ( n ) 和 ( j = 1 ) 到 ( W )。

5. 最终结果：

   • ( dp[n][W] ) 存储的是最大价值。

Java代码实现

下面是使用动态规划解决01背包问题的Java代码示例：

public class Knapsack {
    public static int knapsack(int W, int n, int[] w, int[] v) {
        int[][] dp = new int[n+1][W+1];
        
        // 初始化dp数组
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= W; j++) {
            dp[0][j] = 0;
        }
        
        // 动态规划填表
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= W; j++) {
                if (j >= w[i-1]) {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        
        // 返回最大价值
        return dp[n][W];
    }
    
    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int capacity = 8;
        
        int maxProfit = knapsack(capacity, weights.length, weights, values);
        System.out.println("The maximum profit is " + maxProfit);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

在这段代码中，我们使用了一个二维数组 dp 来存储每一步的结果，并通过逐步计算填充这个表格，最终在 dp[n][W] 中得到背包能够装载

的最大价值。