首页 - 资讯 - 科技 - 教育 - 汽车 - 财经 - 健康 - 房产 - 文旅 - 娱乐 - 游戏
维修 |车展 |报价 |行情 |时评 |新车 |建材 |政策 |市场 |建筑 |家装 |访谈 |股票 |创投人物 |产业 |金融
当前位置： 首页> 汽车> 报价 > 企业网站制作怎么做_北京搬家公司大全_网络推广平台公司_个人博客登录入口

企业网站制作怎么做_北京搬家公司大全_网络推广平台公司_个人博客登录入口

时间:2025/7/14 4:26:22来源：https://blog.csdn.net/2301_78843337/article/details/146556358 浏览次数: 1次
企业网站制作怎么做_北京搬家公司大全_网络推广平台公司_个人博客登录入口
头像
⭐️个人主页：@小羊
⭐️所属专栏：算法
很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

动图描述

目录

    • 1、01背包
      • 【模板】01背包
      • 分割等和子集
      • 目标和
      • 最后一块石头的重量 II
      • 一和零
      • 盈利计划
    • 2、完全背包
      • 【模板】完全背包
      • 零钱兑换
      • 零钱兑换 II
      • 完全平方数
    • 3、似包非包
      • 组合总和 Ⅳ
      • 不同的二叉搜索树

1、01背包

【模板】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表的时候都只依赖上一行的数据，因此可以用两个数组滚动来完成填表的工作，而如果我们从右往左填表从而避免数据被覆盖的话，用一个数组就能轻松完成任务。

所以以上面的代码利用滚动数组做空间优化只需要两步：

  1. 删除掉dp表的横坐标；
  2. 修改填表顺序。
#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

  • 最后一块石头的重量 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

  • 零钱兑换 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];}
};

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~

头像
关键字：企业网站制作怎么做_北京搬家公司大全_网络推广平台公司_个人博客登录入口

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

责任编辑：
>> 相关文章
>> 热门图片
南宁定制网站制作价格_开发公司工程部绩效考核管理办法_网站快速优化排名_在线视频用什么网址
南宁定制网站制作价格_开发公司工程部绩效考核管理办法_网站快速优化排名_在线视频用什么网址
crm管理系统软件_网页ui设计师培训_怎么查权重查询_企业网站管理系统怎么操作
crm管理系统软件_网页ui设计师培训_怎么查权重查询_企业网站管理系统怎么操作
杭州产品网络推广方案_软件开发包括哪些_网站排名优化软件联系方式_浏阳廖主任打人案
杭州产品网络推广方案_软件开发包括哪些_网站排名优化软件联系方式_浏阳廖主任打人案
官方新闻平台有哪些_低价网站建设费用多少_百度指数下载手机版_网站收录大全
官方新闻平台有哪些_低价网站建设费用多少_百度指数下载手机版_网站收录大全
安卓手机app开发工具_中小型企业网络部署_seo优化网站优化_小辉seo
安卓手机app开发工具_中小型企业网络部署_seo优化网站优化_小辉seo
网络运维工程师面试题及答案_今日新闻头条新闻今天_做一个推广网站大概多少钱_正规的培训机构有哪些
网络运维工程师面试题及答案_今日新闻头条新闻今天_做一个推广网站大概多少钱_正规的培训机构有哪些
网站的内容规划怎么写_在线登录qq聊天入口_欧洲网站服务器_网络推广的手段
网站的内容规划怎么写_在线登录qq聊天入口_欧洲网站服务器_网络推广的手段
免费申请pos_开放平台是什么意思_查看别人网站的访问量_推广资源网
免费申请pos_开放平台是什么意思_查看别人网站的访问量_推广资源网
>> 热门搜索
评论排行
图片新闻
更多>>
成都线上超市有哪些平台_昆明大型网站建设费用_seo软件优化工具软件_如何建造一个网站
南充房产信息网官网二手房_杭州市建设委员会_市场调研报告怎么写的_自己建网站要多少钱
平台推广怎么写_web前端自学网站_广州市网络seo外包_免费b2b推广网站
深圳广告公司画册设计_百度竞价项目_网络搭建是干什么的_如何进行app推广
点击排行

邮箱：809451989@qq.com 网站地图
未经过本站允许,请勿将本站内容传播或复制