从二维做法开始
static void Main(string[] args)
{
int[] v = { 1, 2, 3, 4};
int[] w = { 2, 4, 4, 5 };
int target = 5;
// 1. dp[i, j]表示, 从[1, i]的元素中(对应v和w中下标[0, i - 1])任意取使得总体积不超过target并且价值总和最大
// 一般LeetCode中题目都是下标从0开始, 所以下面的例子都是下标从0开始, 和y总的模板有些区别
// dp数组一般会多开一行一列, 防止出现i = 0, i - 1时还需要判断
// 在C#中有两种数组表示方式, int[][]数组的元素和维度可以不同, 每行需要单独new一个数组
// int[,]是矩阵数组, 初始化的时候会赋默认值
int[,] dp = new int[v.Length + 1, target + 1];
for (int i = 1; i <= v.Length; i++)
{
for (int j = 1; j <= target; j++)
{
// 从两个方向推导出dp[i, j]
// 1. 不放物品i, 即背包容量为j, 里面不放物品i的最大价值, dp[i, j] = dp[i - 1, j];
// 2. 放物品i, 即背包容量为j, 里面放物品i的最大价值, 没放物品i的时候就是dp[i - 1, j - v[i - 1]]
// 放入物品i之后, dp[i, j] = dp[i - 1, j - v[i - 1]] + w[i - 1];
// 需要注意的是, 如果物品i放入之后, 容量超出j了, 也就是放不下该物品, 需要排除
// 也可以考虑dp[i - 1, j - v[i - 1]], 数组索引肯定要大于等于0(j - v[i - 1] >= 0)
// 最终结果就是两种情况的最大值
dp[i, j] = dp[i - 1, j];
if (j >= v[i - 1])
{
dp[i, j] = Math.Max(dp[i, j], dp[i - 1, j - v[i - 1]] + w[i - 1]);
}
Console.Write($"{dp[i, j]} ");
}
Console.WriteLine();
}
// dp数组内容
// 2 2 2 2 2
// 2 4 6 6 6
// 2 4 6 6 8
// 2 4 6 6 8
Console.WriteLine(dp[v.Length, target]);
}
空间优化
static void Main(string[] args)
{
int[] v = { 1, 2, 3, 4};
int[] w = { 2, 4, 4, 5 };
int target = 5;
// 通过上面的输出可以发现, dp[i, j]的值取决于上一行dp[i - 1, j]和dp[i - 1, j - v[i - 1]] + w[i - 1]
// 这样就可以优化掉一维
int[] dp = new int[target + 1];
for (int i = 1; i <= v.Length; i++)
{
for (int j = target; j >= v[i - 1]; j--)
{
// 因为v[i - 1] > 0, j - v[i - 1]一定小于j
// 如果j从小到大遍历, dp[j - v[i - 1]]一定先被赋值
// 这样的话dp[j]使用的dp[j - v[i - 1]]就不是上一层的值, 已经被覆盖掉了
// 所以j需要倒序遍历
dp[j] = Math.Max(dp[j], dp[j - v[i - 1]] + w[i - 1]);
Console.Write($"{dp[j]} ");
}
Console.WriteLine();
}
// 2 2 2 2 2
// 4 6 6 6
// 6 6 8
// 6 8
Console.WriteLine(dp[target]);
}
练习题
LeetCode 416. 分割等和子集
LeetCode 1049. 最后一块石头的重量 II