零背零、時間與成果的最佳策略

一個老問題：
有一件物品價值15（W）元沉噩，現(xiàn)在有貨幣價值100元、50元昆禽、20元尚粘、10元择卦、5元、1元郎嫁，每張價值的貨幣張數(shù)不限
請問：如何用最小的貨幣張數(shù)秉继，湊出價值W元？

貪婪策略

這樣一個老生常談的問題泽铛，根據(jù)個人的生活體會尚辑，當(dāng)我們?nèi)】梢匀〉淖畲竺骖~，肯定是能最快的縮短到達W元的張數(shù)盔腔。這種思考方式又稱作貪婪策略杠茬。

15元的貪婪策略

可以看到，當(dāng)W=15時铲觉，W=10+5（兩張）澈蝙，大家完全可以拍著大腿說，兩張撵幽，那肯定是最優(yōu)算法灯荧，畢竟一張的情況已經(jīng)被排除了。如果我們在放大W的值盐杂，當(dāng)W=76時逗载，W=50+20+5+1（四張），可以看到貪婪策略只取當(dāng)前最優(yōu)解的做法链烈，非常優(yōu)秀厉斟，極其有利于快速找到一個可接受的解（有些情況下貪婪策略會導(dǎo)致無解，需要另一種思路的支持强衡，魚之后會說）擦秽。
貪婪策略追求的是局部最優(yōu)解，假設(shè)我們加入另一種貨幣11元，此時當(dāng)W=15時感挥，W=11+1+1+1+1（五張）缩搅，這種就叫撿了西瓜丟了一地芝麻，正如他的名字一樣触幼，這就是貪婪的真實面目硼瓣。甚至說有可能發(fā)生貪婪到最后解決不了問題的情況發(fā)生。不可能所有的問題都能簡單的期望單純的追求局部最優(yōu)解最后的結(jié)果也是最優(yōu)解置谦。

窮舉策略

15元的窮舉策略

當(dāng)沒有辦法直接找到最優(yōu)解決方案時堂鲤，另一種策略誕生了：窮舉。即算出所有結(jié)果的可能性媒峡，然后記下最優(yōu)解瘟栖。這種方法思路簡單且明確，尤其是計算機發(fā)達的今天丝蹭，如果不追求效率慢宗，建個模型扔給電腦，讓它慢慢窮舉奔穿，只要不是過于復(fù)雜很快也能得到答案镜沽。游魚突然回想起以前做有些選擇題，全部帶入求解贱田，正是窮舉的表現(xiàn)缅茉，凡是可以把選項帶入求解的絕對不會錯，而且若果有多選男摧，也是不會錯過正確答案蔬墩。窮舉給算法墊底了底線，假設(shè)你設(shè)計的算法效率和窮舉一個樣耗拓，為何不用窮舉呢拇颅？

大多數(shù)情況下，我們不可以容忍非最優(yōu)解乔询，甚至是有可能無法求解樟插，似乎窮舉成為了我們唯一的路。但是窮舉的時間復(fù)雜度是我們無法忍受的「偷螅現(xiàn)在來思考一下為什么貪婪策略的大問題的最優(yōu)解無法由小問題的局部最優(yōu)解推導(dǎo)出來黄锤？

一、最優(yōu)子結(jié)構(gòu)

依然是原來的問題：

貨幣問題

假設(shè)我們要湊出的價值W所需要的貨幣張數(shù)是f(w)食拜，當(dāng)我們用貪婪時鸵熟，我們?nèi)〉慕馐莊(w)=1+f(4)，f(4)=4负甸。貪婪策略自以為是把f(4)定義成了小問題的最優(yōu)解流强。很明顯在取一張的情況下痹届，我們要考慮的還有如下幾種情況：

三個可能的最優(yōu)解

二、重疊子問題

遞歸和循環(huán)是最簡單的重疊子問題瑞妇！重疊子問題的關(guān)鍵點就在f(n)可以由f(n-1)求得稿静，當(dāng)然可能并不是簡單的多項式關(guān)系，因為多項式關(guān)系已經(jīng)被前面的遞歸和循環(huán)攔住了辕狰，自然不需要高級的求解技巧改备。
回到最開始的問題，貨幣回歸到100元蔓倍、50元悬钳、20元、10元偶翅、5元默勾、1元，解得價值W的最優(yōu)策略聚谁！

#!/usr/bin/C#
//雖然此貨幣結(jié)構(gòu)已經(jīng)是貪婪策略下的最優(yōu)解了母剥，但還是練習(xí)一下，畢竟這個算簡單的
//這個方法是前面解析子結(jié)構(gòu)而得到的垦巴，與網(wǎng)上流行的方法有些不太一樣媳搪。
using System;

namespace ConsoleApplication4
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("目前的貨幣政策，請用逗號隔開骤宣、統(tǒng)一單位秦爆、只要數(shù)字");
            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("目前需要湊到的金額數(shù)");
            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];//這邊屬于無法湊出的金額憔披。所以當(dāng)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[]))在前面循環(huán)已經(jīng)求得解或者是無解，那么自然min(f(m))也就無解或者就是min(f(m-money[]))+1
                {
                    if (i >= money[j]) cost = min(cost, dp[i- money[j]] +1);
                }
                dp[i] = cost;
            }
            
//此時dp的下角標就是對應(yīng)金額的解望门，這里沒高興輸出形娇。
            Console.ReadLine();
        }
        static int min(int a,int b)//取最小值
        {
            return a > b ? b : a;
        }
    }
}

我們來回顧下此處的邏輯：
首先金錢的面額被我們存到數(shù)組money[]里面了，其次我們定義dp[i]=0,i=0（dp表示解）筹误，當(dāng)0<i<min(money[])定義無解桐早。然后我們根據(jù)f(w)=n+f(m)就可以逐步求解：即f[w]=1+min[f(m-money[?])]。最后就可以得到f(w),w=W的值了厨剪。

動態(tài)規(guī)劃入門杰作：背包問題

（這里只介紹下01背包問題哄酝，如果大家還有興趣以下有個網(wǎng)站可以學(xué)習(xí)思路，更加復(fù)雜的思路）
詳詢動態(tài)思考的藝術(shù)

經(jīng)典的背包問題

前面的貨幣問題讓俺們知道了祷膳，用動態(tài)規(guī)劃解決問題就是要優(yōu)化出諸如f(w)=n+f(m)的形式（即找出問題的子結(jié)構(gòu)）陶衅，然后才是想怎么解得f(m)的最優(yōu)解。那么如何化解出最優(yōu)子結(jié)構(gòu)直晨？

最優(yōu)子結(jié)構(gòu)

記得前面的貨幣問題嗎搀军？魚來重復(fù)一下，就是不是就呼之欲出呢勇皇？（其實這就是個不一定要湊滿的貨幣問題只不過衡量標準不同導(dǎo)致構(gòu)造子問題的方法不同）
初步解法：
等價轉(zhuǎn)化：前i個物品放到體積為v的背包當(dāng)中=max((前i-1個物品放入體積為v的背包當(dāng)中),(前i-1個物品放入體積為(v-第i件物品的體積)的背包當(dāng)中+第i件物品的價值))

情況詳解

復(fù)習(xí)一下前面的：
n個貨幣湊出價值w = 1 + min(n-1張貨幣湊出價值w-剔除的那張貨幣的價值)

魚只能說罩句，多多接觸，一定能摸索出盲湊最優(yōu)子結(jié)構(gòu)的能力儒士。

#!/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]);
                }
            }

優(yōu)化解法：
第一個方法在估算價值時的止，緯度涉及到了物品數(shù)量和體積，時空復(fù)雜度為o(VI)着撩，難道不可以像貨幣問題一樣降低復(fù)雜度嗎诅福？比如只用一維數(shù)組記錄每個V對應(yīng)的最優(yōu)解？
基本可以確認方法肯定是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):#對應(yīng)v的最大價值
#為何此處v要倒序拖叙？因為我們求解求的是max((前i-1個物品放入體積為v的背包當(dāng)中),(前i-1個物品放入體積為(v-第i件物品的體積)的背包當(dāng)中+第i件物品的價值))氓润，想一下如果不倒序，此時應(yīng)該是max((前i-1個物品放入體積為v的背包當(dāng)中),(前i個物品放入體積為(v-第i件物品的體積)的背包當(dāng)中+第i件物品的價值))薯鳍，因為因為正序咖气，(v-第i件物品的體積)的實際內(nèi)容已經(jīng)不是(前i-1個物品放入體積為(v-第i件物品的體積)的背包當(dāng)中+第i件物品的價值))了
        dp[j] = max(dp[j], dp[j - w[i-1]] + v[i-1])
print(dp)

如此帶入動態(tài)規(guī)劃的思想。前路漫漫