【算法】动态规划：背包问题
1、01背包
【模板】01背包
(1) 定义状态 dp[i][j] 表示在前 i 个物品中挑选，总体积不超过 j 的所有选法中，最大的价值。
(2) 定义状态 dp[i][j] 表示在前 i 个物品中挑选，总体积刚好等于 j 的所有选法中，最大的价值。
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, V;
int dp[N][N], v[N], w[N];
int main()
{
cin >> n >> V;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
// (1)
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= V; j++)
{
dp[i][j] = dp[i - 1][j];
if (j >= v[i])
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
}
}
cout << dp[n][V] << endl;
// (2)
memset(dp, 0, sizeof dp);
for (int i = 1; i <= V; i++) dp[0][i] = -1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= V; j++)
{
dp[i][j] = dp[i - 1][j];
if (j >= v[i] && dp[i - 1][j - v[i]] != -1)
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
}
}
cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
return 0;
}| 利用滚动数组做优化：
通过观察状态转移方程不难发现，在每次填dp表的时候都只依赖上一行的数据，因此可以用两个数组滚动来完成填表的工作，而如果我们从右往左填表从而避免数据被覆盖的话，用一个数组就能轻松完成任务。
所以以上面的代码利用滚动数组做空间优化只需要两步：
- 删除掉dp表的横坐标；
- 修改填表顺序。
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, V;
int dp[N], v[N], w[N];
int main()
{
cin >> n >> V;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
// (1)
for (int i = 1; i <= n; i++)
for (int j = V; j >= v[i]; j--)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
cout << dp[V] << endl;
// (2)
memset(dp, 0, sizeof dp);
for (int i = 1; i <= V; i++) dp[i] = -1;
for (int i = 1; i <= n; i++)
for (int j = V; j >= v[i]; j--)
if (dp[j - v[i]] != -1)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
return 0;
}分割等和子集
题目本质就是能否从数组中找一个元素和为原数组和一半的子集，属于01背包问题。
定义状态 dp[i][j] 表示能否从前 i 个元素中找若干个和刚好为 j 的子集。
优化前代码：
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size(), sum = 0;
for (int e : nums) sum += e;
if (sum % 2) return false;
int m = sum / 2;
vector<vector<bool>> dp(n + 1, vector<bool>(m + 1));
for (int i = 0; i <= n; i++) dp[i][0] = true;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
dp[i][j] = dp[i - 1][j];
if (j >= nums[i - 1]) dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
}
return dp[n][m];
}
}; 滚动数组优化后代码：
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size(), sum = 0;
for (int e : nums) sum += e;
if (sum % 2) return false;
int m = sum / 2;
vector<bool> dp(m + 1);
dp[0] = true;
for (int i = 1; i <= n; i++)
for (int j = m; j >= nums[i - 1]; j--)
dp[j] = dp[j] || dp[j - nums[i - 1]];
return dp[m];
}
}; 目标和
int m = (target + sum) / 2;
dp[i][j] 表示前 i 个数中选总和正好等于 j，总共有多少种选法。
nums[i] 有可能为0，因此要特别注意初始化。
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int n = nums.size(), sum = 0;
for (int e : nums) sum += e;
int m = (target + sum) / 2;
if (m < 0 || (target + sum) % 2) return 0;
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
dp[0][0] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= m; j++)
{
dp[i][j] = dp[i - 1][j];
if (j >= nums[i - 1]) dp[i][j] += dp[i - 1][j - nums[i - 1]];
}
}
return dp[n][m];
}
};class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int n = nums.size(), sum = 0;
for (int e : nums) sum += e;
int m = (target + sum) / 2;
if (m < 0 || (target + sum) % 2) return 0;
vector<int> dp(m + 1);
dp[0] = 1;
for (int i = 1; i <= n; i++)
for (int j = m; j >= nums[i - 1]; j--)
dp[j] += dp[j - nums[i - 1]];
return dp[m];
}
};最后一块石头的重量 II
本质就是尽可能地按照石头的重量两等分，返回最小的差值。
定义状态 dp[i][j] 表示在前 i 个石头中挑选，重量不超过 j 的最大和。
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = 0;
for (int e : stones) sum += e;
int m = sum / 2;
int n = stones.size();
vector<int> dp(m + 1);
for (int i = 1; i <= n; i++)
for (int j = m; j >= stones[i - 1]; j--)
dp[j] = max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);
return sum - 2 * dp[m];
}
};一和零
dp[i][j][k] 表示从前 i 个字符串中挑选0的个数不超过 j，1的个数不超过 k 的最大子集的长度。
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
int len = strs.size();
vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));
for (int i = 1; i <= len; i++)
{
int a = 0, b = 0;
for (auto e : strs[i - 1])
if (e == '0') a++;
else b++;
for (int j = 0; j <= m; j++)
{
for (int k = 0; k <= n; k++)
{
dp[i][j][k] = dp[i - 1][j][k];
if (j >= a && k >= b)
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - a][k - b] + 1);
}
}
}
return dp[len][m][n];
}
};优化后的代码：
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
int len = strs.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int i = 1; i <= len; i++)
{
int a = 0, b = 0;
for (auto e : strs[i - 1])
if (e == '0') a++;
else b++;
for (int j = m; j >= a; j--)
for (int k = n; k >= b; k--)
dp[j][k] = max(dp[j][k], dp[j - a][k - b] + 1);
}
return dp[m][n];
}
};盈利计划
dp[i][j][k] 表示从前 i 个计划中选，总人数不超过 j，总利润至少为 k 的选法。
关于初始化，没有任务没有利润的选择只有一种。
class Solution {
public:
int profitableSchemes(int n, int m, vector<int>& g, vector<int>& p)
{
const int mod = 1e9 + 7;
int len = g.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
for (int i = 0; i <= n; i++) dp[i][0] = 1;
for (int i = 1; i <= len; i++)
for (int j = n; j >= g[i - 1]; j--)
for (int k = m; k >= 0; k--)
dp[j][k] = (dp[j][k] + dp[j - g[i - 1]][max(0, k - p[i - 1])]) % mod;
return dp[n][m];
}
};2、完全背包
【模板】完全背包
（1）定义状态 dp[i][j] 表示在前 i 个物品中挑选总体积不超过 j 的最大价值。
（2）定义状态 dp[i][j] 表示在前 i 个物品中挑选总体积刚好等于 j 的最大价值。
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, V;
int dp[N][N], v[N], w[N];
int main()
{
// (1)
cin >> n >> V;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= V; j++)
{
dp[i][j] = dp[i - 1][j];
if (j >= v[i])
dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
}
}
cout << dp[n][V] << endl;
// (2)
memset(dp, 0, sizeof dp);
for (int i = 1; i <= V; i++) dp[0][i] = -0x3f3f3f3f;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= V; j++)
{
dp[i][j] = dp[i - 1][j];
if (j >= v[i])
dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
}
}
cout << (dp[n][V] < 0 ? 0 : dp[n][V]) << endl;
return 0;
}注意：一维数组优化01背包是从右往左填表，因为根据状态转移方程可知在填表的过程中依赖的是上一行的数据；而优化完全背包是从左往右填表，根据状态转移方程可知在填表的过程中依赖的是同行的数据。
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, V;
int dp[N], v[N], w[N];
int main()
{
// (1)
cin >> n >> V;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++)
for (int j = v[i]; j <= V; j++)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
cout << dp[V] << endl;
// (2)
memset(dp, 0, sizeof dp);
for (int i = 1; i <= V; i++) dp[i] = -0x3f3f3f3f;
for (int i = 1; i <= n; i++)
for (int j = v[i]; j <= V; j++)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
cout << (dp[V] < 0 ? 0 : dp[V]) << endl;
return 0;
}零钱兑换
定义状态 dp[i][j] 表示从前 i 个硬币中挑选，总和正好等于 j 的所有选法中，最少的硬币个数。
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
const int N = 0x3f3f3f3f;
vector<int> dp(amount + 1, N);
dp[0] = 0;
for (int i = 1; i <= n; i++)
for (int j = coins[i - 1]; j <= amount; j++)
dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);
return dp[amount] >= N ? -1 : dp[amount];
}
};零钱兑换 II
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<unsigned int> dp(amount + 1);
dp[0] = 1;
for (int e : coins)
for (int j = e; j <= amount; j++)
dp[j] += dp[j - e];
return dp[amount];
}
};完全平方数
dp[i][j] = min(dp[i - 1][j], dp[i][j - i * i] + 1);
class Solution {
public:
int numSquares(int n) {
int m = sqrt(n);
vector<int> dp(n + 1, 0x3f3f3f3f);
dp[0] = 0;
for (int i = 1; i <= m; i++)
for (int j = i * i; j <= n; j++)
dp[j] = min(dp[j], dp[j - i * i] + 1);
return dp[n];
}
};3、似包非包
组合总和 Ⅳ
虽然题目说是求组合，但根据示例可知实际让我们求的是排列数。因为背包问题解决的是组合问题，所以这道题只能用类似背包问题的解法解决。
我们需要从nums中找一些排列刚好组成target，则对于某个排列，假设最后一个位置是nums[i]，我们只需要从nums[i]中找一些排列刚好组成target-nums[i]即可。
定义状态 dp[i] 表示总和为 i 时的排列数。
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<unsigned int> dp(target + 1);
dp[0] = 1;
for (int i = 1; i <= target; i++)
for (int e : nums)
if (i >= e)
dp[i] += dp[i - e];
return dp[target];
}
};不同的二叉搜索树
定义状态 dp[i] 表示当节点为 i 时一共有多少种二叉搜索树。
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n + 1);
dp[0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
dp[i] += dp[j - 1] * dp[i - j];
return dp[n];
}
};本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-03-28，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
