C#使用动态规划解决0-1背包问题实例分析

C#使用动态规划解决0-1背包问题实例分析

1. 什么是0-1背包问题？

0-1背包问题是一种典型的NP完全问题，指的是有一个固定容量的背包，若干个物品，每个物品有自己的价值和重量。将部分物品装进背包，使背包装下的物品总价值最大。其中每个物品要么放入背包中，要么不放入，不能拆分物品进行装载。

2. 解决0-1背包问题的动态规划算法

动态规划算法是一种求解复杂问题的有效算法，其核心思想在于将问题分解成若干个子问题进行求解。对于0-1背包问题，动态规划算法可以用以下方式进行求解：

• 状态定义：定义一个二维数组dp[i][j]，表示在前i个物品中能够装入容量为j的背包的最大价值；
• 状态转移：对于第i个物品，如果不放入背包，则背包价值为dp[i-1][j]；如果放入背包，则背包价值为dp[i-1][j-w[i]] + v[i]；
• 初始状态：dp[0][j]=0，dp[i][0]=0，表示没有物品或没有容量时的最大价值均为0；
• 最终结果：dp[n][W]即为0-1背包问题的最优解。

3. C#实现0-1背包问题的动态规划算法

按照上述动态规划算法进行C#代码的实现：

public static int knapsack(int[] w, int[] v, int W)
{
    int[,] dp = new int[w.Length + 1, W + 1];

    for (int i = 1; i <= w.Length; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            if (j < w[i - 1])
            {
                dp[i, j] = dp[i - 1, j];
            }
            else
            {
                dp[i, j] = Math.Max(dp[i - 1, j], dp[i - 1, j - w[i - 1]] + v[i - 1]);
            }
        }
    }

    return dp[w.Length, W];
}

4. 示例一：求解0-1背包问题

现有一个容量为W=10的背包，共有5个物品，重量和价值分别为：

物品	重量	价值
1	2	6
2	2	10
3	6	12
4	5	18
5	4	3

按照上述代码进行调用，求解背包能够承载的最大价值：

int[] w = new int[] { 2, 2, 6, 5, 4 };
int[] v = new int[] { 6, 10, 12, 18, 3 };
int W = 10;

int maxVal = knapsack(w, v, W);

Console.WriteLine($"0-1背包问题的最优解为：{maxVal}"); // 输出：0-1背包问题的最优解为：37

5. 示例二：求解0-1背包问题的路径

在示例一的基础上，修改代码为保存求解路径：

public static int[] knapsack(int[] w, int[] v, int W, out int maxVal)
{
    int n = w.Length;
    int[,] dp = new int[n + 1, W + 1];

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            if (j < w[i - 1])
            {
                dp[i, j] = dp[i - 1, j];
            }
            else
            {
                dp[i, j] = Math.Max(dp[i - 1, j], dp[i - 1, j - w[i - 1]] + v[i - 1]);
            }
        }
    }

    maxVal = dp[n, W];

    int[] path = new int[n];
    int count = 0;
    for (int i = n; i > 0; i--)
    {
        if (dp[i, W] > dp[i - 1, W])
        {
            path[count++] = i - 1; // 加入物品i-1
            W -= w[i - 1]; // 更新背包容量
        }
    }

    return path.Take(count).ToArray();
}

按照上述代码进行调用，求解背包能够承载的最大价值和所选物品的编号：

int[] w = new int[] { 2, 2, 6, 5, 4 };
int[] v = new int[] { 6, 10, 12, 18, 3 };
int W = 10;

int[] path = knapsack(w, v, W, out int maxVal);

Console.WriteLine("背包能够承载的最大价值为：" + maxVal);
Console.Write("选中的所有物品编号为：");
foreach (int p in path)
{
    Console.Write($"{p+1} ");
}
// 输出：背包能够承载的最大价值为：37
//       选中的所有物品编号为：1 2 4