零、时间与成果的最佳策略
一个老问题：
有一件物品价值15（W）元，现在有货币价值100元、50元、20元、10元、5元、1元，每张价值的货币张数不限
请问：如何用最小的货币张数，凑出价值W元？
贪婪策略
这样一个老生常谈的问题，根据个人的生活体会，当我们取可以取的最大面额，肯定是能最快的缩短到达W元的张数。这种思考方式又称作贪婪策略。
15元的贪婪策略
可以看到，当W=15时，W=10+5（两张），大家完全可以拍着大腿说，两张，那肯定是最优算法，毕竟一张的情况已经被排除了。如果我们在放大W的值，当W=76时，W=50+20+5+1（四张），可以看到贪婪策略只取当前最优解的做法，非常优秀，极其有利于快速找到一个可接受的解（有些情况下贪婪策略会导致无解，需要另一种思路的支持，鱼之后会说）。
贪婪策略追求的是局部最优解，假设我们加入另一种货币11元，此时当W=15时，W=11+1+1+1+1（五张），这种就叫捡了西瓜丢了一地芝麻，正如他的名字一样，这就是贪婪的真实面目。甚至说有可能发生贪婪到最后解决不了问题的情况发生。不可能所有的问题都能简单的期望单纯的追求局部最优解最后的结果也是最优解。
穷举策略
15元的穷举策略
当没有办法直接找到最优解决方案时，另一种策略诞生了：穷举。即算出所有结果的可能性，然后记下最优解。这种方法思路简单且明确，尤其是计算机发达的今天，如果不追求效率，建个模型扔给电脑，让它慢慢穷举，只要不是过于复杂很快也能得到答案。游鱼突然回想起以前做有些选择题，全部带入求解，正是穷举的表现，凡是可以把选项带入求解的绝对不会错，而且若果有多选，也是不会错过正确答案。穷举给算法垫底了底线，假设你设计的算法效率和穷举一个样，为何不用穷举呢？
大多数情况下，我们不可以容忍非最优解，甚至是有可能无法求解，似乎穷举成为了我们唯一的路。但是穷举的时间复杂度是我们无法忍受的。现在来思考一下为什么贪婪策略的大问题的最优解无法由小问题的局部最优解推导出来？
一、最优子结构
依然是原来的问题：
货币问题
假设我们要凑出的价值W所需要的货币张数是f(w)，当我们用贪婪时，我们取的解是f(w)=1+f(4)，f(4)=4。贪婪策略自以为是把f(4)定义成了小问题的最优解。很明显在取一张的情况下，我们要考虑的还有如下几种情况：
三个可能的最优解
鱼瞬间发现一个问题：贪婪策略的问题在于当最优子结构不定时，因为贪婪策略一味的追求最大的11元，忽视了他的f(4)并不是最优子结构。假设对于任意的W都有f(w)=n+f(m)，当n为定值，最小的m对应最小的f(m)，那么贪婪策略瞬间成为最优策略。
此时最小的f(m)就成为了最优子结构，而n为定值，所以f(w)这个大问题也就迎刃而解了。关键点就在于n为定值，这点又有人称这种现象叫无后继性。
二、重叠子问题
递归和循环是最简单的重叠子问题！重叠子问题的关键点就在f(n)可以由f(n-1)求得，当然可能并不是简单的多项式关系，因为多项式关系已经被前面的递归和循环拦住了，自然不需要高级的求解技巧。
回到最开始的问题，货币回归到100元、50元、20元、10元、5元、1元，解得价值W的最优策略！
#!/usr/bin/C#
//虽然此货币结构已经是贪婪策略下的最优解了，但还是练习一下，毕竟这个算简单的
//这个方法是前面解析子结构而得到的，与网上流行的方法有些不太一样。
using System;
namespace ConsoleApplication4
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("目前的货币政策，请用逗号隔开、统一单位、只要数字");
string lines = Console.ReadLine();
string [] line = lines.Split(',');
int[] money = new int[line.Length];
Array.Sort(money);
for (int i = 0;i< line.Length; i++)
{
money[i] = int.Parse(line[i]);
}
Console.WriteLine("目前需要凑到的金额数");
int aim = int.Parse(Console.ReadLine());
int[] dp = new int[aim+1];//用来记录dp下角标所标识的金额最小解。
int cost;
for(int m = 1; m <= money[0]; m++) dp[m] = money[money.Length-1];//这边属于无法凑出的金额。所以当dp的值大于等于max(money[])时说明此金额无法凑出。
for (int i= money[0]; i<= aim;i++)//从最小的可凑金额min(money[])开始计算每个金额的最小解。
{
cost = int.MaxValue;
for(int j = 0;j< money.Length; j++)//这里的思路就是：因为是从最小的可凑金额开始的min(f(m)) = 1+min(f(m-money[])),其中min(f(m-money[]))在前面循环已经求得解或者是无解，那么自然min(f(m))也就无解或者就是min(f(m-money[]))+1
{
if (i >= money[j]) cost = min(cost, dp[i- money[j]] +1);
}
dp[i] = cost;
}
//此时dp的下角标就是对应金额的解，这里没高兴输出。
Console.ReadLine();
}
static int min(int a,int b)//取最小值
{
return a > b ? b : a;
}
}
}
我们来回顾下此处的逻辑：
首先金钱的面额被我们存到数组money[]里面了，其次我们定义dp[i]=0,i=0（dp表示解），当0<i<min(money[])定义无解。然后我们根据f(w)=n+f(m)就可以逐步求解：即f[w]=1+min[f(m-money[?])]。最后就可以得到f(w),w=W的值了。
动态规划入门杰作：背包问题
（这里只介绍下01背包问题，如果大家还有兴趣以下有个网站可以学习思路，更加复杂的思路）
详询动态思考的艺术
经典的背包问题
前面的货币问题让俺们知道了，用动态规划解决问题就是要优化出诸如f(w)=n+f(m)的形式（即找出问题的子结构），然后才是想怎么解得f(m)的最优解。那么如何化解出最优子结构？
最优子结构
记得前面的货币问题吗？鱼来重复一下，就是不是就呼之欲出呢？（其实这就是个不一定要凑满的货币问题只不过衡量标准不同导致构造子问题的方法不同）
初步解法：
等价转化：前i个物品放到体积为v的背包当中=max((前i-1个物品放入体积为v的背包当中),(前i-1个物品放入体积为(v-第i件物品的体积)的背包当中+第i件物品的价值))
情况详解
复习一下前面的：
n个货币凑出价值w = 1 + min(n-1张货币凑出价值w-剔除的那张货币的价值)
鱼只能说，多多接触，一定能摸索出盲凑最优子结构的能力。
#!/usr/bin/C#
int W =15;
int[] w = { 5, 4, 7, 2, 6 };
int[] v = { 5, 3, 10, 3, 7 };
int[,] dp = new int[v.Length+1,W+1];
for (int i = 1; i <= v.Length; i++)
{
for (int j = 0; j <= W; j++)
{
if (j < w[i-1]) dp[i,j] = dp[i - 1,j];
else dp[i,j] = max(dp[i - 1,j], dp[i - 1,j - w[i-1]] + v[i-1]);
}
}
优化解法：
第一个方法在估算价值时，纬度涉及到了物品数量和体积，时空复杂度为o(VI)，难道不可以像货币问题一样降低复杂度吗？比如只用一维数组记录每个V对应的最优解？
基本可以确认方法肯定是f[v]=max{f[v],f[v-c[i]]+w[i]}
#!/usr/bin/python
w=(5,4,7,2,6)
v=(5,3,10,3,7)
W = 15
dp = [0 for i in range(W+1)]
#初始化空间
for i in range(1,len(w)+1):#取一件物品到取i件物品
for j in range(len(dp)-1,w[i-1]-1,-1):#对应v的最大价值
#为何此处v要倒序？因为我们求解求的是max((前i-1个物品放入体积为v的背包当中),(前i-1个物品放入体积为(v-第i件物品的体积)的背包当中+第i件物品的价值))，想一下如果不倒序，此时应该是max((前i-1个物品放入体积为v的背包当中),(前i个物品放入体积为(v-第i件物品的体积)的背包当中+第i件物品的价值))，因为因为正序，(v-第i件物品的体积)的实际内容已经不是(前i-1个物品放入体积为(v-第i件物品的体积)的背包当中+第i件物品的价值))了
dp[j] = max(dp[j], dp[j - w[i-1]] + v[i-1])
print(dp)
如此带入动态规划的思想。前路漫漫
网友评论