课程总结第十一周 （背包）

先学完经典DP后，再学背包，感觉学起来轻松了很多。看了很多背包的博客，已经讲的的特别清楚。感觉我就没太大必要再去写原理、做分类，简要的总结下背包的分类模板，重点是做题的收获和学到的技巧。

01背包收获：（几类特殊的01背包） 1 求背包价值最大问题: n个物品每个都有它的价值和容量，要求在一个固定的容量内，所得物品的价值最大。

两种代码实现： 1.dp [i][j]表示前i个物品装入容量为j的背包所得的最大价值。问题点在于第i件物品装与不装所得到最大值的比较。

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

2.采用一维数组，从容量最大开始装，每次装入都更新上一个状态所得到的最大值。

dp[j]=max(dp[j],dp[j-c[i]]+w[i]          // j=v （最大容量）

骨头问题一 ：是一个01背包的裸题，跳过。 骨头问题二 ：在01背包的基础上，要求输出第k个最大值，较难处理。（题D） 我的思路：想再开个数组去记录出现的所有值，再进行降序排列，然后执行去重操作，感觉确实可行，因为此时装入物品只考虑价值，也就是即使能装入第i个物品，但要求第k个最大值，也会选择不去装。 思路二：开两个数组每次循环分别记录第i个物品装入前，和装入后的价值量。dp[j][kk]表示容量为j时第kk个最值。if(dp[j][kk]!=dp[j][kk-1]) kk++;这个语句控制每次循环数组中出现的大量重复值，只记录一个。由于k只到30，所以虽然代码效率不高，但影响不大。 关键代码：（不太了解归并思想，所以开始理解有点困难）

            while(kk=b[y])
                    {dp[j][kk]=a[x];x++;}
                else
                    {dp[j][kk]=b[y];y++;}
                if(dp[j][kk]!=dp[j][kk-1])
                    kk++;
            }

2.背包求价值最小问题： 一个人去抢银行，每个银行都带有两个属性，可抢得的钱数和被抓的风险，再被抓的风险小于给定值时能抢得的钱数最多。（题C）

我的思路：1.首先确定，每个银行只能被抢一次，确定为01背包。2.由于给定被抓概率和每个银行被抓概率。确定每个银行被抓的概率要小于给定的，不然会被抓。然后简单的认为只要能抢得银行概率相加小于给定的，求出最大值即可。（这里就想错了）

正确做法：概率加减没有意义，要反过来想，用想抢的银行不被抓的概率相乘大于给定的不被抓的概率。 初始化：将dp数组请0，dp[0]=1（所抢金额为0时，自然不会被抓）。这里的i表示能抢得金额数。

 dp[0]=1;  //很关键
       for(int i=1;i=mj[i];j--)
           {
               dp[j]=max(dp[j],dp[j-mj[i]]*pj[i]);
           }
       }

类似题目： 有 n 个学校可以填报， 第i个学校的费用 w [ i ] ，获得 offer 的概率 p [ i ] ，问在有 m 万美元预算的情况下，至少收到一封 offer 的最大概率是多少。---->>>可转化为一封都收不到的最大概率是多少。

3. 01背包中下标出现负数（题R） 我的思路：开始并不知道这种处理方式，但注意到有两类变量。一类是牛的智商要尽量大，牛的情商也要相应大，使得总和最大。如果只是处理一种最值的话，很好解决。我并没有好的想法。

正解：用下标记录牛的情商，而dp[i]则表示牛的智商。由于下表出现负数，范围是-100000到100000，所以同时加100000，因此用100000来划分正负区间。初始化的技巧：将除了0之外的下标都赋值为无穷，则dp[i]的含义需要注意，每次更新值都有特殊含义。

完全背包收获： 一个物品可以取任意次。好多题目都是求分配方案。 1.给定不同面额的金币，再给定一个指定金额，问有多少中搭配方案。（每种面额金币任意取） H题 我的思路：由于是求方案数，dp[i]表示金额为i时有多少种方案数。dp[j]+=dp[j-m[i]];不断累加。 初始化：dp[0]=1,0元也是一种搭配方案，只是不需要面额钱。

2.同样是金钱搭配方案问题，算是变型。（I题）由于要搭配的钱出现小数，要扩大相应倍数，但要注意精度问题。此外有些输出格式必须要用c语言。

int nn=int(n*100+0.5);  //起到控制精度的作用
printf("%6.2f%17lld\n",n,dp[nn]);
//c语言输出，保留两位小数。和long long位数组

3.k种面额（1，2，……，k）n元钱，有多少种搭配方案。 高精度大数处理 。注意：当n为1000时，k=100，结果为32个整数，取值范围已经超过了long long范围。 处理方式：采用两个long long数组搭配输出。若超过18位，对第一个数组进行 除inf 的操作，第二个数组进行对inf取余的操作”%”。 注意：要先除再取余，顺序不能反！！

       for(int i=1;i