0 - 1 背包问题介绍
0 - 1 背包问题是一个经典的组合优化问题，属于 NP 完全问题。问题描述如下：
给定一组物品，每个物品有对应的重量 w[i] 和价值 v[i]，以及一个容量为 C 的背包。要求在不超过背包容量的前提下，选择一些物品放入背包，使得背包中物品的总价值最大。这里的“0 - 1”表示对于每个物品，只能选择放入背包（1）或者不放入背包（0），不能只放入部分物品。
解决思路 - 动态规划
虽然贪心算法在某些情况下可以用于解决近似问题，但对于 0 - 1 背包问题，动态规划是一种能得到最优解的有效方法。动态规划的核心思想是将原问题分解为子问题，并保存子问题的解，避免重复计算。
设 dp[i][j] 表示前 i 个物品放入容量为 j 的背包中所能获得的最大价值。状态转移方程如下：
- 当
j < w[i - 1]时（即当前背包容量不足以放入第i个物品）：dp[i][j] = dp[i - 1][j] - 当
j >= w[i - 1]时（即当前背包容量可以放入第i个物品）：dp[i][j] = Math.Max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1])
C# 代码实现
using System;class KnapsackProblem
{public static int Knapsack(int capacity, int[] weights, int[] values){int n = weights.Length;int[,] dp = new int[n + 1, capacity + 1];for (int i = 1; i <= n; i++){for (int j = 1; j <= capacity; j++){if (weights[i - 1] > j){dp[i, j] = dp[i - 1, j];}else{dp[i, j] = Math.Max(dp[i - 1, j], dp[i - 1, j - weights[i - 1]] + values[i - 1]);}}}return dp[n, capacity];}
}class Program
{static void Main(){int[] weights = { 2, 3, 4, 5 };int[] values = { 3, 4, 5, 6 };int capacity = 8;int maxValue = KnapsackProblem.Knapsack(capacity, weights, values);Console.WriteLine("背包能装下的最大价值为: " + maxValue);}
}
代码解释
Knapsack方法接收背包容量capacity、物品重量数组weights和物品价值数组values作为参数。- 使用二维数组
dp来保存子问题的解。 - 通过两层循环遍历所有物品和所有可能的背包容量，根据状态转移方程更新
dp数组。 - 最终返回
dp[n, capacity]，即前n个物品放入容量为capacity的背包中所能获得的最大价值。
在 Main 方法中，定义了物品的重量、价值和背包容量，调用 Knapsack 方法计算并输出背包能装下的最大价值。
