「手撕算法」锁定大厂看这就可

0/1背包问题是另外两种背包问题的基础，简单描述一下，假设有个背包，载重上限为W，此时有n个物品，第i个物品的重量是wi，价值为vi，那么在不超过背包重量上限的前提下，能获得的最大物品价值总和?同样我们采用四步走的方式

状态定义

首先分析背包问题中的自变量和因变量，其中因变量比较好确定，就是所求最大价值总和，自变量呢，在此自变量为物品种类和背包承重上限，因为这两者会影响价值总和的最大值，所以我们设置一个二维状态。dp[i][j]代表使用前i个物品，背包最大载重为j的情况下最大价值总和。

状态方程

说白了就是找映射函数，dp[i][j]的表达式。我们将dp[i][j]分为两大类，第一类是不选择第i个物品最大价值和，第二类为选择了第i个物品的最大价值和。然后在两者中选择最大值就是价值更大的方案。

如果选择第i个物品，此时的最大价值为dp[i-1][j-wi]+vi，既然选择了第i个商品，那么就需要留出一个位置，那么此时对于剩余的i-1个商品的载重空间就只剩下j-wi了，此时i-1个物品选择的最大价值和为dp[i-1][j-wi]，然后加上vi就是当前获得最大价值和。所以转移方程为

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])

正确性证明

首先dp[0][j]=0，意味着没有物品的时候，无论背包限重多少，能够得到的最大价值和都是0，所以k0争取

其次，假设我们已经获取i-1个物品的价值最大值，所有dp[i-1]的值，那么根据状态方程，我们能知道所有dp[i]的值

最后两步联合，整个求解对于任意dp[i][j]成立

实现 #define MAX_V 10000 #define MAX_N 100 int v[MAX_N + 5], w[MAX_N + 5]; int dp[MAX_N + 5][MAX_V + 5]; int get_dp(int n, int W) {     // 初始化 dp[0] 阶段     for (int i = 0; i <= W; i++) dp[0][i] = 0;     // 假设 dp[i - 1] 成立，计算得到 dp[i]     // 状态转移过程，i 代表物品，j 代表背包限重     for (int i = 1; i <= n; i++) {            for (int j = 0; j <= W; j++) {         // 不选择第 i 种物品时的最大值         dp[i][j] = dp[i - 1][j];         // 与选择第 i 种物品的最大值作比较，并更新         if (j >= w[i] && dp[i][j] < dp[i - 1][j - w[i]] + v[i]) {             dp[i][j] = dp[i - 1][j - w[i]] + v[i];             }         }     }     return dp[n][W]; } 

8 贪心

其实我们大学学习的好几种应用都是采用了贪心的算法啊，比如Huffman Coding，Prim最小生成树等

先来看一道之前美团的一道笔试题--跳一跳

有n个盒子排成一行，每个盒子上面有一个数字a[i]，表示最多能向右跳a[i]个盒子;小林站在左边第一个盒子，请问能否到达最右边的盒子?比如说：[1, 2, 3, 0, 4] 可以到达第5个盒子;[3, 2, 1, 0, 4] 无法到达第5个盒子;

思路：自然而然的想法，尽可能的往右边跳，看最后能够到达，从第一个盒子开始从右遍历，对于每个经过的盒子，不断地更新maxRight值。那么贪心算法的思考过程通常是怎么样的?

类似于动态规划，大事化小，小事化了。所谓大事化小，将大的问题，找到和子问题的重复部分，将复杂问题拆分为小的问题。小事化了，通过对小事的打磨找到较为核心的策略。上例子

分糖果问题

我们有 m 个糖果和 n 个孩子。我们现在要把糖果分给这些孩子吃，但是糖果少，孩子多(m

我的问题是，如何分配糖果，能尽可能满足最多数量的孩子?

对于一个孩子来说，如果小的糖果可以满足，那么就没必要用更大的糖果 对糖果的大小需求的孩子更容易被满足，所以我们可以从需求小得孩子开始分配糖果 因为满足一个需求大的孩子跟满足一个需求小的孩子，对我们期望值的贡献是一样的 我们每次从剩下的孩子中，找出对糖果大小需求最小的，然后发给他剩下的糖果中能满足他的最小的糖果，这样得到的分配方案，也就是满足的孩子个数最多的方案 #include  #include  #include  using namespace std;   /* 解题思路： 遍历两边，首先每个人得一块糖，第一遍从左到右，若当前点比前一个点高就比前者多一块。 这样保证了在一个方向上满足了要求。第二遍从右往左，若左右两点，左侧高于右侧，但 左侧的糖果数不多于右侧，则左侧糖果数等于右侧糖果数+1，这就保证了另一个方向上满足要求。  最后将各个位置的糖果数累加起来就可以了。 */   int candyCount(vector&rating) {      int res = 0;     //孩子总数     int n = rating.size();      //糖果集合     vector candy(n, 1);     //从左往右遍历     for (int i = 0;i < n - 1;i++) {         if (rating[i + 1] > rating[i])candy[i + 1] = candy[i] + 1;     }     //从右往左     for (int i = n - 1;i > 0;i--) {         if (rating[i - 1] > rating[i] && candy[i - 1] <= candy[i])             candy[i - 1] = candy[i] + 1;     }      //累加结果     for (auto a : candy) {         res += a;     }      return res; } //测试函数 int main() {      vector rating{1,3,2,1,4,5,2};     cout << candyCount(rating) << endl;     return 0; } 

（编辑：应用网_阳江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!