公司网站建设流程模板网站的建设

当前位置： 首页 > news >正文

公司网站建设流程,模板网站的建设,网站运营与管理,阿里巴巴 网站建设01背包问题 1. 【模板】01背包2. 分割等和子集3. 目标和4. 最后一块石头的重量 II 01背包问题是一种动态规划问题#xff0c;用于求解在有限容量的背包中装入最大价值的物品组合。具体步骤如下#xff1a; 定义一个二维数组dp[i][j]#xff0c;表示从前i个物品中选择若干个… 01背包问题 1. 【模板】01背包2. 分割等和子集3. 目标和4. 最后一块石头的重量 II 01背包问题是一种动态规划问题用于求解在有限容量的背包中装入最大价值的物品组合。具体步骤如下 定义一个二维数组dp[i][j]表示从前i个物品中选择若干个放入容量为j的背包能得到的最大价值。初始化dp[0][j]和dp[i][0]为0表示没有物品或者没有背包容量时价值为0。遍历每个物品和每个背包容量根据物品的重量和价值更新dp[i][j]。有两种情况1.如果物品i的重量大于背包容量j那么不能放入dp[i][j] dp[i-1][j]即等于前i-1个物品的最大价值。 2.如果物品i的重量小于等于背包容量j那么可以选择放入或者不放入dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])即取放入和不放入中的较大值。最后返回dp[n][V]即前n个物品放入容量为V的背包的最大价值。 二维表和DP数组在背包问题中都扮演着重要的角色但它们各自的作用是不同的。 二维表在背包问题中我们通常使用二维表来记录子问题的解。二维表的大小通常为(m1) × (W1)其中m是物品的数量W是背包的容量。每个单元格表示对于给定的容量和物品集合可以得到的最大价值。通过填充这个二维表我们可以得到背包问题的最优解。 DP数组DP数组是背包问题中最核心的部分它用于存储每个状态的最优解。DP[i][j]代表当只有前i个物品且背包容量为j时可以得到的最大价值。通过填充DP数组我们可以得到背包问题的最优解。 总的来说二维表可以看作是DP数组的“地图”它告诉我们应该如何填充DP数组以得到最优解。而DP数组则是实际计算最优解的地方。

1. 【模板】01背包 1.题目链接【模板】01背包 2.题目描述 你有一个背包最多能容纳的体积是V。现在有n个物品第i个物品的体积为vi ,价值为wi。 1求这个背包至多能装多大价值的物品 2若背包恰好装满求至多能装多大价值的物品 输入描述 第一行两个整数n和V表示物品个数和背包体积。 接下来n行每行两个数vi和wi表示第i个物品的体积和价值。 1≤n,V,vi,wi ≤1000。 输出描述 输出有两行第一行输出第一问的答案第二行输出第二问的答案如果无解请输出0。 示例1 输入 3 5 2 10 4 5 1 4 输出14 9 说明装第一个和第三个物品时总价值最大但是装第二个和第三个物品可以使得背包恰好装满且总价值最大。 示例2 输入 3 8 12 6 11 8 6 8 输出 8 0 说明 装第三个物品时总价值最大但是不满装满背包无解。 3.问题分析上题大概意思是对于每一个物品都有一个体积Vi和价值Wi现在有一个背包体积为V所以需要用两个一维数组将物品的体积和价值管理起来然后求1求这个背包至多能装多大价值的物品2若背包恰好装满求至多能装多大价值的物品 然后就按上述解法进行状态表示该dp[i][j]表示从前i个物品中选择若干个放入容量为j的背包能得到的最大价值。即脑海中想象出一个二维表该表的横坐标表示的是背包的容量V纵坐标表示的是背包中物品的总价值W。 状态表示dp[i][j]表示从前i个物品中选择若干个放入容量为j的背包能得到的最大价值。状态转移方程1求这个背包至多能装多大价值的物品对于每一个物品来说它只有被选择和不被选择两种结果而选择需要先判断背包的容量够不够所以可以先处理不选择该物品如果不选那么dp[i][j] dp[i-1][j]如果选择则说明背包的容量可以大于该物品的体积即j - v[i] 0将该物品选择后并且在i-1选择物品的前几个物品选择最大的价值这块如果想更好的理解那么建议画一画dp数组即dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])。2若背包恰好装满求至多能装多大价值的物品若背包恰好装满又该如何那么就在加条件即可对于第一问的dp表可以将背包不满的位置设为-1如果dp表某位置为-1那么不选即可。初始化因为对于求 ij 位置的值需要知道 i - 1j - w[i]位置的值根据以往的经验可以多设置一行和一列防止越界访问。对第一问来说装不了的物品就dp位置设置为0所以全部初始化为0即可。而对于第二问来说没装满的位置设置为-1所以需要细分一下dp表的第一行表示的是背包的个数为0–n个而物品的体积为0所以除了0,0位置刚好装满其余没装满即除了0,0位置为0其余位置初始化为-1dp表的第一列表示的是物品的体积为0而背包的个数为0–n个所以全初始化为0。填表顺序从左往右从上到下依次填写。返回值返回dp[n][v]位置的值第二问dp[n][v]可能是-1所以在这判断一下如果为-1返回0。 4.代码如下 #include stdio.h #include iostream #include string.h using namespace std;const int N 1010; int n, V, v[N], w[N]; int dp[N][N];int main() {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 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;memset(dp, 0, sizeof dp); // 将dp表进行清零for (int j 1; j V; j)dp[0][j] -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; }2. 分割等和子集 1.题目链接分割等和子集 2.题目描述 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。 示例 1 输入nums [1,5,11,5] 输出true 解释数组可以分割成 [1, 5, 5] 和 [11] 。 示例 2 输入nums [1,2,3,5] 输出false 解释数组不能分割成两个元素和相等的子集。 提示 1 nums.length 200 1 nums[i] 100 3.题目分析这道题是将一个数组分割成两个子集使得两个子集的元素和相等。可以这样转换一下将这个数组求和然后除以2求出数组的分割成两个子集的和接下来就是在nums数组中选择一些数使得这些被选数的和刚好等于数组总和的一半。这样这道题就是一个01背包问题。 状态表示dp[i][j]表示选择前i个数中的某些值这些数的和刚好为j。状态转移方程对于dp表的ij位置的数来说可能有选和不选两种结果如果不选那么dp[i][j] dp[i - 1][j]如果选的话那么需要判断背包所剩的空间够不够选这个数这个数在第i个位置有j个空间体积为nums[i]即 j nums[i]那么dp[i][j] max(dp[i][j], dp[i - 1][j - nums[i]]);初始化和上述第二问一样就不在解释了。填表顺序从左往右从上到下依次填写。返回值如果dp[n][v]-1返回false否则返回true。 4.代码如下 class Solution { public:bool canPartition(vectorint nums) {int n nums.size();int sum 0;for (auto x : nums)sum x;if (sum % 2 1)return false;int v sum / 2;vectorvectorint dp(n 1, vectorint(v 1));for (int j 1; j v; j) // 初始化dp[0][j] -1;for (int i 1; i n; i){for (int j 1; j v; j){dp[i][j] dp[i - 1][j];if (j nums[i - 1] dp[i - 1][j - nums[i - 1]] ! -1) // nums[i - 1]是因为增加了一行和一列nums要对应dp的关系所以i-1dp[i][j] max(dp[i][j], dp[i - 1][j - nums[i - 1]]);}}if (dp[n][v] ! -1)return true;elsereturn false;} };3. 目标和 1.题目链接目标和 2.题目描述 给你一个非负整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 ‘’ 或 ‘-’ 然后串联起所有整数可以构造一个 表达式
   例如nums [2, 1] 可以在 2 之前添加 ‘’ 在 1 之前添加 ‘-’ 然后串联起来得到表达式 “2-1”。 返回可以通过上述方法构造的、运算结果等于 target 的不同。 示例 1 输入nums [1,1,1,1,1], target 3 输出5 解释一共有 5 种方法让最终目标和为 3 。 -1 1 1 1 1 3 1 - 1 1 1 1 3 1 1 - 1 1 1 3 1 1 1 - 1 1 3 1 1 1 1 - 1 3 示例 2 输入nums [1], target 1 输出1 提示 1 nums.length 20 0 nums[i] 1000 0 sum(nums[i]) 1000 -1000 target 1000 3.问题分析我们需要给数组中的数添加正负号使得它们的和等于所给的target对于每一个数来说有正有负那么每多一个数就会多2^n中可能所以不好暴力求解。但我们将nums中的正数、负数分别看作一部分设为ab那么a b suma - b target可以算出a (sum target) / 2那么是不是就可以看作是在nums数组中找一些数使得这些数的和为a(即带正号的数)这样这道题就和上道题基本一致了。 状态表⽰dp[i][j] 表⽰在前 i 个数中选总和正好等于 j ⼀共有多少种选法。状态转移⽅程根据最后⼀个位置的元素有选择最后⼀个元素或者不选择最后⼀个元素两种策略1. 不选 nums[i] dp[i][j] dp[i - 1][j] 2. 选择 nums[i] 这种情况下是有前提条件的此时的 nums[i] 应该是⼩于等于j 。因为如果这个元素都⽐要凑成的总和⼤选择它就没有意义呀。那么我们能够凑成总和为j 的⽅案数就要看在前 i - 1 个元素中选能否凑成总和为 j - nums[i] 。根据状态表⽰此时dp[i][j] dp[i - 1][j - nums[i]]。初始化由于需要⽤到上⼀⾏的数据因此可以先把第⼀⾏初始化。第⼀⾏表⽰不选择任何元素要凑成⽬标和 j 。只有00符合要求所以第⼀⾏仅需初始化第⼀个元素 dp[0][0] 1 。填表顺序 根据「状态转移⽅程」我们需要「从上往下」填写每⼀⾏每⼀⾏的顺序是「⽆所谓的」。返回值返回 dp[n][a] 的值。其中n 表⽰数组的⼤⼩ a表⽰要凑的⽬标和。 4.代码如下 class Solution { public:int findTargetSumWays(vectorint nums, int target) {int n nums.size();int sum 0;for (auto x : nums)sum x;int v (sum target) / 2;if (v 0 || (sum target) % 2)return 0;vectorvectorint dp(n 1, vectorint(v 1));dp[0][0] 1;for(int i 1; i n; i) // 填表for(int j 0; j v; 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][v];} };4. 最后一块石头的重量 II 1.题目链接最后一块石头的重量 II 2.题目描述 有一堆石头用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合从中选出任意两块石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 x y。那么粉碎的可能结果如下 如果 x y那么两块石头都会被完全粉碎 如果 x ! y那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为 y-x。 最后最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下就返回 0。 示例 1 输入stones [2,7,4,1,8,1] 输出1 解释 组合 2 和 4得到 2所以数组转化为 [2,7,1,8,1]组合 7 和 8得到 1所以数组转为 [2,1,1,1] 组合 2 和 1得到 1所以数组转化为 [1,1,1] 组合 1 和1得到 0所以数组转化为 [1]这就是最优值。 示例 2 输入stones [31,26,33,21,40] 输出5 提示 1 stones.length 30 1 stones[i] 100 3.问题分析将石头两两进行粉碎两两粉碎也就是找两个数进行相减将相减的数看作两部分sum记为所有数的和要使得这两部分的数尽可能的相等那么是不是就是在所有数中尽可能找一些数使得它们的和接近于sum的一半这样就可以看作有一个背包容量为sum / 2尽可能将sum装满即可。 4.代码如下 class Solution { public:int lastStoneWeightII(vectorint stones) {int n stones.size();int sum 0;for (auto x : stones)sum x;int v sum / 2;vectorvectorint dp(n 1, vectorint(v 1));for (int i 1; i n; i){for (int j 0; j v; j){dp[i][j] dp[i - 1][j];if (j stones[i - 1])dp[i][j] max(dp[i][j], dp[i - 1][j - stones[i - 1]] stones[i - 1]);}}return sum - 2 * dp[n][v];} };