做ppt比较好的网站,python可以做网站前台么,焦作网站建设哪家公司好,app开发常用软件文章目录 [模版]01背包1. 第一问: 背包不一定能装满(1) 状态表示(2) 状态转移方程(3) 初始化(4) 填表顺序(5) 返回值 2. 第二问: 背包恰好装满3. 空间优化 416.分割等和子集1. 状态表示2. 状态转移方程3. 初始化4. 填表顺序5. 返回值 [494. 目标和](https://leetcode.cn/proble… 文章目录 [模版]01背包1. 第一问: 背包不一定能装满(1) 状态表示(2) 状态转移方程(3) 初始化(4) 填表顺序(5) 返回值 2. 第二问: 背包恰好装满3. 空间优化 416.分割等和子集1. 状态表示2. 状态转移方程3. 初始化4. 填表顺序5. 返回值 [494. 目标和](https://leetcode.cn/problems/target-sum/description/)1. 状态表示2. 状态转移方程3. 初始化4. 填表顺序5. 返回值 1049.最后一块石头的重量II1. 状态表示2. 状态转移方程3. 初始化4. 填表顺序5. 返回值 [模版]01背包 1. 第一问: 背包不一定能装满
(1) 状态表示
dp[i][[j]: 从前 i 个物品中挑选, 总体积不超过 j, 所有选法中, 能挑选出来的最大价值.
(2) 状态转移方程
根据最后一步的状况, 分情况讨论:
不选 i 物品 此时就是在前 i-1 个物品中挑选, 总体积不超过 j, 所有选法中, 能挑选出来的最大价值. dp[i][j] dp[i-1][j] 选 i 物品 选了 i 物品, 说明最后要加上 w[i], 此时就是在前 i-1 个物品中挑选, 总体积不超过 j - v[i], 所有选法中, 能挑选出来的最大价值. dp[i][j] dp[i-1][ j - v[i] ] w[i] 注:j-v[i]可能不存在, 所以 j-v[i] 0 比如, j 1, 但是 v[i] 4 了, 此时 j-v[i] 为 负数了, 就是不存在的.
综上, 状态转移方程为: dp[i][j] max(dp[i-1][j], dp[i-1][j-v[i]] w[i]) (3) 初始化
根据题意可知, 下标是从 1 开始的, 所以 dp表 会多一行多一列. 横坐标代表物品数, 纵坐标代表体积. 第0行表示: 从前0个物品中挑选, 总体积不超过 j 的最大价值, 就是为0. 第0列表示: 从前 i 个物品中挑选, 总体积不超过 0 的最大价值, 物品都是有体积的, 这种情况也不存在, 也是为0.
所以可以不用特别的初始化, 默认为0即可.
(4) 填表顺序
从上往下
(5) 返回值
根据状态表示可知, 题目最终要返回的是, 从前 n 个物品中挑选, 总体积不超过 v 的最大价值. 即返回: dp[n][v].
2. 第二问: 背包恰好装满
与第一问的讨论思路和过程是一模一样, 状态转移方程也一样, 只有以下几点有细微的变化:
(1) 状态表示 dp[i][[j]: 从前 i 个物品中挑选, 总体积恰好等于 j, 所有选法中, 能挑选出来的最大价值.
(2) 判断状态方程是否存在 在求每一个状态时, 从前 i-1 个物品中选,可能会选不出体积恰好等于 j 的物品. 此时可以做一个约定: dp[i][j] -1时, 表示没有这种情况. 其实在第一种情况 不选 i 物品时, 是可以不用特判 dp[i-1][j] ! -1的. 因为第一种情况不选 i 物品是一定存在的, 如果 dp[i-1][j] -1, 那么 dp[i][j] -1, 这是合理的. 但是第二种情况 选 i 物品时一定要特判 dp[i-1][j-v[i]] ! -1. 因为第二种情况多加了一个 w[i], 如果 dp[i-1][j-v[i]] 等于 -1, 再加上 w[i], 就会影响最终结果了.
(3) 初始化 第一个格子为0 , 因为正好能凑齐体积为0 的背包, 但是第一行后面的格子都是 -1 , 因为没有物品, 无法满足体积大于 0 的情况.
(4) 返回值 最后有可能凑不出体积恰好为 V 的,所以返回之前要特判一下.
代码实现如下:
#include iostream
#include cstring
using namespace std;const int N 1010;
int n, V;
int v[N], w[N];
int dp[1010][1010];int main()
{cin n V;for(int i 1; i n; i) //下标从1开始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] 0)dp[i][j] max(dp[i-1][j], dp[i-1][j-v[i]] w[i]);}}cout dp[n][V] endl;//解决第二问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] 0 dp[i-1][j-v[i]] ! -1)dp[i][j] max(dp[i-1][j], dp[i-1][j-v[i]] w[i]);}}cout (dp[n][V] -1 ? 0 : dp[n][V]) endl;return 0;
}3. 空间优化
1.利用滚动数组做空间上的优化 2.直接在原始的代码上修改即可 步骤: 1.把二维dp表中的 i (所有横坐标)去掉改成一维(不是改成一层循环,还是需要两层循环,只是把dp表中的 i 去掉). 2.修改 j 的遍历顺序成从右往左. 修改后的代码如下:
#include iostream
#include cstring
using namespace std;const int N 1010;
int n, V;
int v[N], w[N];
int dp[1010];int main()
{cin n V;for(int i 1; i n; i) //下标从1开始cin v[i] w[i];//解决第一问for(int i 1; i n; i){for(int j V; j 0; j--){dp[j] dp[j];if(j - v[i] 0)dp[j] max(dp[j], dp[j-v[i]] w[i]);}}cout dp[V] endl;//解决第二问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 0; j--){dp[j] dp[j];// 注意要特判if(j - v[i] 0 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;
}416.分割等和子集 1. 状态表示
dp[i][j]:从前 i 个数中选,和是否恰好等于 j ,是为true, 不是为false.
2. 状态转移方程
和01背包问题一样, 根据第 i 个位置选或不选,分两种情况讨论: (1) 不选第 i 个数: dp[i][j] dp[i-1][j] (2) 选第 i 个数: dp[i][j] dp[i-1][j-nums[i]] 只要这两种选法中有一个能凑成就是符合题意的, 所以可得: dp[i][j] dp[i-1][j] || dp[i-1][j-nums[i]] 注意: j - nums[i] 0.
3. 初始化
为了防止填表时出现越界问题,一般还是多开一行多开一列. (0, 0) 位置, 从前 0 个数中选,和是否恰好等于 0, 成立, 所以是 true, 第一行的其他位置则为 false. 第一列, 从前 i 个数中选,和是否恰好等于 0, 成立, 所以第一列初始化为 true.
4. 填表顺序
从上往下.
5. 返回值
本题可以转化为: 在数组中选一些数, 让这些数的和等于 sum / 2.(其中sum是整个数组的和). 所以最终返回: dp[n][sum / 2] 即可.
代码实现如下:
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;vectorvectorbooldp(n1, vectorbool(sum1));for(int j 1; j sum; j) dp[0][j] false;for(int i 0; i n; i) dp[i][0] true;for(int i 1; i n; i){for(int j 1; j sum; j){dp[i][j] dp[i-1][j];if(j - nums[i-1] 0)dp[i][j] dp[i-1][j] || dp[i-1][j-nums[i-1]];}}return dp[n][sum/2];}
};空间优化后的代码如下:
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;vectorbooldp(vectorbool(sum1));for(int j 1; j sum; j) dp[j] false;for(int i 0; i n; i) dp[0] true;for(int i 1; i n; i){for(int j sum; j 1; j--){dp[j] dp[j];if(j - nums[i-1] 0)dp[j] dp[j] || dp[j-nums[i-1]];}}return dp[sum/2];}
};494. 目标和 我们先对这道题进行分析: 在添加完±号后会有正数和负数,我们把所有正数和记为a,所有负数和的绝对值记为b,总和记为sum. 根据题意可知: a-btarget, absum,可得 a (sumtarget)/2
所以原题可转换为:在数组中选一些数让这些数字的和等于a一共有多少种选法. 这就是一个01背包问题, 下面的分析过程和上一题 [416.分割等和子串] 基本一样.
1. 状态表示
dp[i][j]:从前 i 个数中选使得总和为 j 一共有多少种选法.
2. 状态转移方程
根据i位置的状态有两种情况 1.i 位置不选dp[i][j] dp[i-1][j] 2.i 位置选dp[i][j] dp[i-1][j-nums[i]] 注意: j nums[i]. 综上两种选法的总数: dp[i][j] dp[i-1][j] dp[i-1][j-nums[i]]
3. 初始化
依旧是多加一行多加一列. 第一行:数组里没有元素要凑成和为0,和为1… 都凑不出, 所以填 0, 但是 dp[0][0] 1. 第一列:除了第一个位置其余位置是可以不用特别初始化的. 因为本题的数字有可能是0,第一列表示的是从前 i 个数字中总和为0的选法,那就会有很多种情况了。 而我们初始化的目的就是避免填表时越界访问而选第 i 个位置时是用第二种情况,这种情况我们有前提条件 j nums[i]当 j 0 时, 要使用那个方程就要满足 nums[i] 0, 此时 dp[i][j] dp[i-1][0], 这使得这种情况填表时只会使用表中的上一个位置而不是越界访问。
4. 填表顺序
从上往下
5. 返回值
根据我们上面的分析可知, 最终返回: dp[n][a] 即可.
代码实现如下:
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int n nums.size();int sum 0;for(auto x : nums) sum x;int a (sum target) / 2;if(a 0 || (sum target) % 2 1) return 0;vectorvectorint dp(n1, vectorint(a1));dp[0][0] 1;for(int i 1; i n; i){for(int j 0; j a; 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][a];}
};空间优化后的代码如下:
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int n nums.size();int sum 0;for(auto x : nums) sum x;int a (sum target) / 2;if(a 0 || (sum target) % 2 1) return 0;vectorint dp(vectorint(a1));dp[0] 1;for(int i 1; i n; i){for(int j a; j 1; j--){dp[j] dp[j];if(j nums[i-1])dp[j] dp[j-nums[i-1]];}}return dp[a];}
};1049.最后一块石头的重量II 我们先来分析题目: 挑选两个石头粉碎其实就是在任意两个石头前添加±号 分析思路同目标和一题全部正数和记为a,负数和绝对值记为b. 要求的就是|a-b|的最小值。 而我们又知道全部数的总和sum, 即absum. 求|a-b|的最小值可以说成: 把一个数sum拆成两个数求这两个数的差的最小值. 而只有当这两个数越接近sum/2时差就越小 综上分析本题可转换为: 在数组中选择一些数让这些数的和尽可能接近sum/2(这些数的和就是上面的a或b). 本质就是一个01背包问题: 物品 - 数 每个物品的价值 - nums[i] 每个物品体积 - nums[i] 背包体积 - sum/2. 选一些数放进背包中在不超过背包体积的情况下里面的最大和是多少. 1. 状态表示
dp[i][j]:从前i个数中选总和不超过j,此时的最大和.
2. 状态转移方程
根据i位置的状态有两种情况 1.i 位置不选dp[i][j] dp[i-1][j] 2.i 位置选dp[i][j] dp[i-1][j-nums[i]] nums[i] 注意: j nums[i]. 综上: dp[i][j] max(dp[i-1][j] , dp[i-1][j-nums[i]])
3. 初始化
多一行多一列 第一行:背包中没有石头无法凑成总和为0,1,2,3… 初始化为0即可 第一列:同 [目标和] 一题.
4. 填表顺序
从上往下
5. 返回值
dp[n][sum/2] 就是上面分析中的 a则 b sum-dp[n][sum/2], 所以最小值为 a - b sum - 2 * dp[n][sum/2].
代码实现如下:
class Solution
{
public:int lastStoneWeightII(vectorint stones) {int n stones.size(), sum 0;for(auto x : stones) sum x;vectorvectorint dp(n1, vectorint(sum / 2 1));for(int i 1; i n; i){for(int j 0; j sum / 2; j){dp[i][j] dp[i-1][j];if(j stones[i-1])dp[i][j] max(dp[i-1][j], dp[i-1][j-stones[i-1]] stones[i-1]);}}// dp[n][sum/2]就是上面分析中的a则bsum-dp[n][sum/2]// 所以最小值为a-bsum - 2 * dp[n][sum/2]return sum - 2 * dp[n][sum/2];}
};空间优化后的代码:
class Solution
{
public:int lastStoneWeightII(vectorint stones) {int n stones.size(), sum 0;for(auto x : stones) sum x;vectorint dp(vectorint(sum / 2 1));for(int i 1; i n; i){for(int j sum / 2; j 1; j--){dp[j] dp[j];if(j stones[i-1])dp[j] max(dp[j], dp[j-stones[i-1]] stones[i-1]);}}// dp[n][sum/2]就是上面分析中的a则bsum-dp[n][sum/2]// 所以最小值为a - b sum - 2 * dp[sum/2]return sum - 2 * dp[sum/2];}
};
