背包问题Ⅱ与二分问题

今天我对背包问题有了更深的理解我一定要写下来巩固自己的思路并且遇到新的难题二分不管了干就完了完全背包以今天写的代码展开详细描述与解释,并附上题目#define N 1001 int n, v, W[N], V[N]; int main() { cin n v; for (int i 1; i n; i) { cin V[i] W[i]; } int dp[N][N]; 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; 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 0; j v; j) { dp[i][j] dp[i - 1][j]; if (j V[i] dp[i][j - V[i]] ! -1) dp[i][j] max(dp[i][j], dp[i][j - V[i]] W[i]); } } cout (dp[n][v] -1 ? 0 : dp[n][v]) endl; return 0; }这是一道在牛客上写的题目所以使用全局的变量更加方便根据输入要求我直接把数组设置的足够大那么就不用考虑越界的问题题目分为两道第一道就是中规中矩的动态规划但是要区别与01背包第二道需要一些数学推导简化代码第一题我们要确定下来状态转移方程dp[i][j]意为在前i个物品中所挑选的物品中总体积不超过j的情况下所能拥有的最大价值这里主要区分与01背包的是dp[i][j] max(dp[i][j],dp[i][j - V[i]] W[i])表达式这里01背包中是dp[i][j] max(dp[i][j],dp[i-1][j - V[i]] W[i])因为完全背包和01背包的本质区别是01背包中物品都只有一个然而完全背包中物品确实可以任意多个所以以我的话来讲就是在01背包中你选了当前物品就不能再次选择了就只能去前i-1个物品中找合适的选项在完全背包中你选了当前物品还可以再次选择了就可以再去前i个物品中找合适的选项第二题我们要确定下来状态转移方程dp[i][j]意为在前i个物品中所挑选的物品中总体积恰好为j的情况下所能拥有的最大价值这题中最重要的是一个数学公式推导还有初始化与返回值问题初始化主要讨论第一行与第一列dp[0][0]就是0不用质疑当i0时要讨论从0个物品中挑选出j体积的情况是不可能出现的所以要把这些位置置为-1(表示不存在这种情况)当j0要讨论从i(从1开始)个物品中挑选出0体积的情况只要不选即可所以情况存在只要置为0即可数学公式推导如下3.因为最终结果可能为-1所以需要特判一下完全背包利用滚动数组优化后的代码#define N 1001 int n, v, W[N], V[N]; int main() { cin n v; for (int i 1; i n; i) cin V[i] W[i]; int dp[N]; memset(dp, 0, sizeof dp); 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; 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[i]; j v; 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背包利用滚动数组优化后的代码#define N 1010 int n, v, M[N], V[N]; int dp[N]; int main() { cin n v; for (int i 1; i n; i) { cin V[i] M[i]; } //第一问 for (int i 1; i n; i) { for (int j v; j V[i]; j--) { dp[j] max(dp[j], M[i] dp[j - V[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 V[i] dp[j - V[i]] ! -1; j--) { dp[j] max(dp[j], M[i] dp[j - V[i]]); } } cout (dp[v] -1 ? 0 : dp[v]) endl;; return 0; }如上可知两份代码有一些细微差别即遍历顺序01背包从右往左因为需要避免重复选取同一个物品我们想象下如果从左往右遍历dp[j]与dp[j-v[i]]的关系如若有一个物品体积为2我们一开始初始化了dp[2]但是当j4时会使得出现dp[j]dp[j-v[i]]的情况(即dp[2]dp[4-2])此时就违背了01背包的原则--物品只能选一次所以应该从右往左遍历这样我们就可以确保不会重复使用到第i个物品完全背包从左往右遍历完全背包则和01背包相反可以重复使用第i个物品所以因该是从左往右遍历详情见上至此01背包和完全背包已经完全解释清楚撒花*★,°*:.☆(▽)/$:*.°★*二分算法二分算法是一类模板题有规范的解题思路所以更应该把思路理清不为了一劳永逸而是加深巩固方便日后复习以之前写的代码展开详细描述与解释,并附上题目class Solution { public: vectorint searchRange(vectorint nums, int target) { if(nums.size()0) { return {-1,-1}; } int begin0; int nnums.size(); int left0,rightn-1; while(leftright) { int midleft(right-left)/2; if(nums[mid]target) { leftmid1; } else { rightmid; } } if(nums[left]!target) { return {-1,-1}; } else { beginleft; } left0,rightn-1; while(leftright) { int midleft(right-left1)/2; if(nums[mid]target) { leftmid; } else { rightmid-1; } } return {begin,right}; } };二分查找算法的本质--二段性即遇到有二段性的题目可以优先尝试使用二分算法确定左右边界在题目中会分为两种左右①leftmid1rightmid//②leftmidrightmid-1在这种情况下所选中的x是小于target与x大于等于target//x是小于等于target与x大于target判断left是否1或者right是否-1即看这个x是否可能是所需答案如若x不是所需答案需要1//-1操作跳过这个数确定中点mid在题目中会分为两种左右①midleft(right-left)/2 || midleft(right-mid1)/2如何区分这两种情况呢很简单我只需要观察right是否-1即可如若-1则括号中需要1反之则不要总结如下图算法进行的前提是leftright总结当xt时right一直向left靠拢当xt时left一直向right靠拢回到开头我们可知对于x的划分是基于二段性的即当我们求左端点时数组会被划分成小于t与大于等于t两个部分当我们求右端点时数组会被划分成大于t与小于等于t两个部分最后感谢您的观看