背包算法在LeetCode中的应用：动态规划解决经典问题

在算法领域中，动态规划（Dynamic Programming，简称DP）是一种极为重要的解题方法，尤其在处理背包问题时表现得尤为突出。背包问题是一类经典且广泛应用的问题，涵盖了许多变体，如0-1背包、完全背包、多重背包等。本文将深入探讨背包算法在LeetCode中的应用，通过几个典型的题目来展示如何使用动态规划解决这些经典问题。

一、理论基础

动态规划的核心思想是通过将复杂问题分解为若干个子问题，并利用子问题的解来构建原问题的解。其关键在于避免重复计算子问题，通常通过存储中间结果来实现。

背包问题的基本概念：

0-1背包：给定一组物品，每种物品只能选择一次，求在总重量不超过背包容量的情况下，总价值最大的组合。
完全背包：每种物品可以选择任意多次，求在总重量不超过背包容量的情况下，总价值最大的组合。
多重背包：每种物品有给定数量的限制，求在总重量不超过背包容量的情况下，总价值最大的组合。

二、LeetCode题目解析

1. 最接近目标价格的甜点成本（LeetCode 1774）

问题描述：给定冰激凌基料和配料成本数组，以及一个目标价格，求组合出总成本尽可能接近目标价格的甜点。

解题思路：

使用多重背包的思想，将每种配料看作一种物品，其数量有限。
定义dp[j]为总成本为j时，最接近目标价格的甜点成本。
状态转移方程：dp[j] = max(dp[j], dp[j - cost[i]] + value[i])，其中cost[i]和value[i]分别为第i种配料的成本和价值。

代码实现：

#include <vector>
#include <algorithm>
using namespace std;

int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
    int maxSum = *max_element(baseCosts.begin(), baseCosts.end()) + *max_element(toppingCosts.begin(), toppingCosts.end()) * 2;
    vector<int> dp(maxSum + 1, INT_MIN);
    dp[0] = 0;

    for (int cost : baseCosts) {
        for (int j = maxSum; j >= cost; --j) {
            dp[j] = max(dp[j], dp[j - cost] + cost);
        }
    }

    for (int cost : toppingCosts) {
        for (int k = 0; k < 2; ++k) { // Each topping can be used at most twice
            for (int j = maxSum; j >= cost; --j) {
                dp[j] = max(dp[j], dp[j - cost] + cost);
            }
        }
    }

    int closest = INT_MAX;
    for (int j = 0; j <= maxSum; ++j) {
        if (dp[j] != INT_MIN && abs(j - target) < abs(closest - target)) {
            closest = j;
        }
    }
    return closest;
}

2. 最小化目标值与所选元素的差（LeetCode 1981）

问题描述：给定一个m x n的整数矩阵和一个目标值，从每行中选取一个整数，使得选中元素的总和与目标值的绝对差最小。

解题思路：

将问题转化为分组背包问题，每行视为一组物品。
定义dp[i][j]为前i行选取元素总和为j时的最小绝对差。
状态转移方程：dp[i][j] = min(dp[i-1][j], dp[i-1][j - nums[k]] + abs(target - (j - nums[k])))，其中nums[k]为第i行的元素。

代码实现：

#include <vector>
#include <climits>
using namespace std;

int minimizeTheDifference(vector<vector<int>>& mat, int target) {
    int m = mat.size(), n = mat[0].size();
    int maxSum = 0;
    for (const auto& row : mat) {
        maxSum += *max_element(row.begin(), row.end());
    }
    vector<vector<int>> dp(m, vector<int>(maxSum + 1, INT_MAX));
    dp[0][0] = 0;

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j <= maxSum; ++j) {
            if (dp[i][j] != INT_MAX) {
                for (int k = 0; k < n; ++k) {
                    if (j + mat[i][k] <= maxSum) {
                        dp[i + 1][j + mat[i][k]] = min(dp[i + 1][j + mat[i][k]], dp[i][j]);
                    }
                }
            }
        }
    }

    int closest = INT_MAX;
    for (int j = 0; j <= maxSum; ++j) {
        if (dp[m][j] != INT_MAX) {
            closest = min(closest, abs(j - target));
        }
    }
    return closest;
}

3. 和为目标值的最长子序列的长度（LeetCode 2915）

问题描述：给定数组nums和一个目标值target，找出数组中和为target的最长子序列的长度。如果不存在这样的子序列，返回-1。

解题思路：

将问题转化为0-1背包问题。
定义dp[j]为和为j时的最长子序列长度。
状态转移方程：dp[j] = max(dp[j], dp[j - nums[i]] + 1)。

代码实现：

#include <vector>
#include <algorithm>
using namespace std;

int longestSubsequence(vector<int>& nums, int target) {
    vector<int> dp(target + 1, -1);
    dp[0] = 0;

    for (int num : nums) {
        for (int j = target; j >= num; --j) {
            if (dp[j - num] != -1) {
                dp[j] = max(dp[j], dp[j - num] + 1);
            }
        }
    }
    return dp[target];
}

三、总结与扩展

通过上述几个LeetCode题目的解析，我们可以看到动态规划在解决背包问题及其变种中的强大威力。无论是0-1背包、完全背包还是多重背包，核心思想都是通过状态转移方程来逐步构建问题的解。

学习建议：

理解基础概念：深入理解动态规划和背包问题的基本概念。
练习经典题目：通过LeetCode上的经典题目进行实践，逐步掌握不同背包问题的解题技巧。
总结归纳：每次解题后进行总结，归纳不同问题的共性和差异。

扩展阅读：

《算法导论》中的动态规划章节
LeetCode官方题解和相关讨论区
线上算法课程和视频教程

希望本文能帮助你在动态规划和背包问题的学习中更进一步，解决更多有趣的算法题目！

全部栏目

背包算法在LeetCode中的应用：动态规划解决经典问题