算法分享（贪婪+动态规划）

算法

办理题目的方法。就好比同样是从长沙到北京，坐火车可能必要几天，坐高铁6小时，坐飞机两个半小时，固然交通工具差别，所消耗的成本也差别，算法就是在成本与时间中不停权衡，一个好的算法权衡标准就是用尽可能小的代价成本实现较短时间到达。
算法有什么用？

<ul>口试大厂必备技能。
更快的性能。盘算机中主要的盘算组件就是CPU，假设某个题目可以通过两种算法(简称为算法1、算法2)办理，它们的时间复杂度分为O(n)和O(n²)，假设如今某型号CPU的运算速度提拔了10倍，我们分别配置稍微低一点的CPU去跑时间复杂度为O(n)的算法，和使用提拔了10倍的CPU去跑时间时间复杂度为O(n²)的算法，我们会发现一个结果：在n>10以后，使用配置低的硬件运行的效率要比配置高的硬件效率更好（假设n=20, CPU1: 20 10.5[/td][td]0.21[/td][/tr][tr][td]30->6[/td][td]0.2[/td][/tr][tr][td]30->5[/td][td]0.18[/td][/tr][tr][td]20->5[/td][td]0.25[/td][/tr][/table]先兑换20->5，再兑换50->11，得15.5个兴币
动态规划(递归+存储)

2030405060708050->10.500010.510.510.510.530->606610.510.510.516.530->506610.5111116.520->5566111115.516.5寻找递推关系式
面对当前场次有两种可能性：
小兴兴余额不敷，总兴币与上一个场次兴币个数一致
小兴兴满赠门槛，但兑换了当前场次不一定是当前最优，所以需判断兑换的兴币是不是最大值
关键代码：

1. int[] w = { 0 , 50 , 30 ,30 , 20 };       //小兴兴兑换值0、50、30、30、20
2. float[] v = { 0 , 10.5f , 6 , 5 , 5 };       //兴币面额 10.5、6、5、5
3. int balance  = 80;                     //用户小兴兴总余额
4. float[][] dp = new float[5][7];               //动态规划表
5. for (int i = 1; i <= 4; i++) {
6.     for (int j = 20; j <= balance ; j+=10) {
7.         if (j < w[i]){
8.             dp[i][j] = dp[i - 1][j];
9.         } else{
10.             dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
11.         }
12.     }
13. }

复制代码

关键代码
[code]for (int i = 1; i