動態(tài)規(guī)劃

動態(tài)規(guī)劃是一種高性能的牛逼算法巴元，由美國的R.Bellman提出毡咏，它是動態(tài)就是體現(xiàn)在此算法是基于一個遞推公式或者說是多個初始公式和遞歸公式，在求解當(dāng)前問題的解時(shí)逮刨，我們只需要按照遞推公式呕缭，直接由上一層結(jié)果推導(dǎo)出來，而不是從頭一步步計(jì)算禀忆，它的效率客觀臊旭，但是它有一個不好的情況，就是難箩退，難在你要通過所給的問題离熏，找出它是否滿足動態(tài)規(guī)劃算法的范疇，難在你要根據(jù)題目找出它的遞推公式戴涝。(我好像說多了滋戳，難也要上)

因?yàn)閯討B(tài)規(guī)劃在課本里面將的時(shí)候，前面全是什么雜七雜八的推導(dǎo)啥刻，看的人頭大奸鸯，此節(jié)我將直接用例題帶你走進(jìn)動態(tài)規(guī)劃，了解它的基本性值和求解一般思路可帽。

問題1：斐波那契數(shù)列

斐波那契數(shù)列定義

Fib(n)=1---------------------------------n=1時(shí)

Fib(n)=1---------------------------------n=2時(shí)

Fib(n)=Fib(n-1)+Fib(n-2)------------n>2時(shí)

我們?nèi)绻凑罩暗淖龇ι褪怯眠f歸求解它，遞歸算法如下

int Fib(int n)
{
    if (n == 1 || n == 2)
    {
        return 1;
    }
    return Fib(n - 1) + Fib(n - 2);
}

現(xiàn)在我們來分析下這個遞歸代碼，假設(shè)我們現(xiàn)在求Fib(5),整個求解過程如下

dt1.jpg

分析:
上面是求Fib(5)的示意圖蓄拣，F(xiàn)ib(5) = Fib(4)+Fib(3),求Fib(4)時(shí)扬虚，由去求Fib(3)+Fib(2),求Fib(3)時(shí)，由去求Fib(2)+Fib(1),我們發(fā)現(xiàn)個問題球恤，就是Fib(3)被重復(fù)計(jì)算了辜昵，如果這個N更大，那么重復(fù)計(jì)算的數(shù)字更多咽斧，這不是提高了時(shí)間復(fù)雜度堪置？我們?nèi)绾谓鉀Q這個重復(fù)計(jì)算問題？我們可以換一種角度思考张惹，是否可以將每次計(jì)算的結(jié)果保存在數(shù)組里舀锨，計(jì)算當(dāng)前問題時(shí)，如果需要用到上一次的值诵叁，直接取出來就ok,不用從頭再來雁竞。好基于這個思路钦椭，我在改造下斐波那契代碼拧额。

int Fib(int n)
{
    int dp[100] = {0};
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= n; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

下面是整個求Fib(5)的流程，對比前面的遞歸彪腔，我們發(fā)現(xiàn)這個就直接取出之前數(shù)據(jù)的結(jié)果侥锦，解決了重復(fù)計(jì)算數(shù)據(jù)的問題。

dt2.jpg

問題2：兩地點(diǎn)最短路徑

假設(shè)A處有一個水庫德挣，現(xiàn)在需要鋪設(shè)一條管道到G處恭垦，邊上的數(shù)字代表距離，現(xiàn)在我們要找出最短的距離格嗅，如何實(shí)現(xiàn)番挺？想到這里，我們既可以用單源最短路徑求法屯掖，又可以用貝爾曼算法玄柏，不過今天我們的主題是動態(tài)規(guī)劃，這個例子可以很好的用動態(tài)思想去求解贴铜。

dt3.jpg

分析：

我們設(shè)置一個dis數(shù)組粪摘，保存當(dāng)前點(diǎn)到A點(diǎn)的最短距離，那么每次我們都去一步步逼近到終點(diǎn)绍坝，當(dāng)我們要計(jì)算當(dāng)前位置到A最短距離時(shí)徘意，我們只需要根據(jù)前面的點(diǎn)，去求得當(dāng)前點(diǎn)的最短距離轩褐，那么我們可以設(shè)計(jì)一個動態(tài)規(guī)劃轉(zhuǎn)移方程 dis[i] = MIN (dis[i-1] + data[i-1] [i]);此處的data就是一個二維矩陣椎咧，存儲每兩個點(diǎn)的距離。

1. 初始dis[A] = 0;
2. 求點(diǎn)B,C,D.
   • dis[B] = dis[A] + AB = 2;(前面只有一個點(diǎn)A)
   • dis[C] = dis[A] + AC = 4;(前面只有一個點(diǎn)A)
   • dis[D] = dis[A] + AD = 3;(前面只有一個點(diǎn)A)
3. 求點(diǎn)E把介，F(xiàn).
   • dis[E] = dis[B] + BE =6,dis[E] = dis[C] + CE = 5,所以dis[E] = 5
   • dis[F] = dis[C] + CF =7,dis[F] = dis[D] + DF = 8,所以dis[F] = 7
4. 求點(diǎn)G
   • dis[G] = dis[E] +EG = 8,dis[G] = dis[F] +FG = 11,所以dis[G] = 8.

最后直接根據(jù)dis[G] = 10,得到了A到G的最短距離是8.此處就完美的解釋了動態(tài)規(guī)劃的思想勤讽。

動態(tài)規(guī)劃初步總結(jié)

根據(jù)上面兩個例子的學(xué)習(xí)竹宋，我們可能大概知道了動態(tài)規(guī)劃的一部分，明白它如何計(jì)算地技，如何實(shí)現(xiàn)真正意義的動態(tài)◎谄撸現(xiàn)在我們整理下用動態(tài)規(guī)劃求解題目的過程和方法。

性質(zhì)

1. 最優(yōu)化性質(zhì)莫矗，問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的飒硅，比如上面兩個問題我們總是先求最優(yōu)子問題的解，然后根據(jù)子問題解逐步逼近到最終解作谚。
2. 無后效性三娩，某狀態(tài)決策一旦確定，那么后面的決策不會影響這個決策妹懒，比如上面我們求子問題的第一步到第n步之間雀监，都是一次性確立，后面不會改變眨唬。
3. 有重疊子問題会前，比如前面兩個問題，它們?nèi)绻凑照Ｋ悸非蠼庳腋停家狼耙浑A段的解瓦宜，前一階段又是同樣的道理，每次都是重復(fù)子問題的累積岭妖。

解題步驟

1. 劃分階段临庇，我們總是將大問題，劃分成小問題昵慌，用小問題解逐步逼近到大問題的解
2. 確定狀態(tài)轉(zhuǎn)移方程假夺，這個是動態(tài)規(guī)劃的關(guān)鍵，看上面的兩個題斋攀，我們都寫出了它的轉(zhuǎn)移方程已卷，轉(zhuǎn)移方程就好比每個子問題的公式，直接套用蜻韭。
3. 尋找邊界悼尾，就是確定算法何時(shí)結(jié)束。

問題3：最大連續(xù)子序列和

問題描述

給定一個有n個整數(shù)的序列肖方，求出其中最大連續(xù)子序列的和闺魏，例如(-2,11,-4,13,-5,-2),它的最大連續(xù)子序列和是20，所構(gòu)成的連續(xù)子序列就是11俯画，-4析桥，13.

求解思路

根據(jù)上面的總結(jié)，我們知道動態(tài)規(guī)劃的核心就是確定動態(tài)轉(zhuǎn)移方程和邊界。本題的動態(tài)轉(zhuǎn)移方程是什么?我們用dp[i]表示當(dāng)前位置的最大連續(xù)子序列和泡仗。

首先第一個邊界條件是dp[0] = 0;
第二個我們可以考慮埋虹，判斷dp[i-1] 加上當(dāng)前的值與當(dāng)前值比較，如果dp[i-1]+data[i]都小于data[i],證明dp[i-1]肯定是個負(fù)數(shù)娩怎，那么肯定越加越小搔课，那么我就沒必要加入前面那個dp[i-1]。直接更新dp[i] = data[i];

總結(jié)的動態(tài)轉(zhuǎn)移方程就是

1. dp[0] = 0------------------------------------i=0
2. max(dp[i-1]+data[i] , data[i])-----------i>0

算法代碼

void maxSum()
{
    int data[] = { 0,-2,11,-4,13,-5,-2 };//0位置不用
    int len = sizeof(data) / sizeof(int);
    int *dp,max=-9999;
    dp = (int *)malloc(sizeof(int) * len);
    dp[0] = 0;
    for (int i = 1; i < len; i++)
    {
        if (dp[i - 1] + data[i] > data[i])
        {
            dp[i] = dp[i - 1] + data[i];
        }
        else
        {
            dp[i] = data[i];
        }
    }

    //直接找出dp數(shù)組最大截亦，就是最大結(jié)果
    for (int i = 0; i < len; i++)
    {
        if (dp[i] > max)
        {
            max = dp[i];
        }
    }
    printf_s("最大連續(xù)子序列和是: %d", max);
}

問題4：三角形最短路徑

問題描述

給定一個高度是n的整數(shù)三角形爬泥，找出從頂部到底部的最短路徑，每個點(diǎn)只能走下一層的相鄰點(diǎn)崩瓤，如下圖袍啡，是一個高度是4的三角形，輸出的最短路徑就是2却桶，3境输，5，3颖系，路徑和是13

dt4.jpg

求解思路

首先我們這個三角形一定是用二維數(shù)組表示的嗅剖，實(shí)際在二維數(shù)組的排列是這樣的，如下圖
首先我們得對比分析上圖集晚，推導(dǎo)每個點(diǎn)可以走的路窗悯，假設(shè)現(xiàn)在坐標(biāo)是(x区匣，y)那么該點(diǎn)往下一層走只能走兩個點(diǎn)(x+1,y+1)和(x+1,y).我們用二維數(shù)組data[i][j]表示每個點(diǎn)坐標(biāo)和值偷拔，用動態(tài)數(shù)組dp[i][j]來表示從頂部0,0走到當(dāng)前點(diǎn)的最短路徑和。接下來我們分析下動態(tài)轉(zhuǎn)移方程和邊界問題亏钩。

1. dp[0][0] = data[0][0]----------------------------------------------------頂部邊界

2. dp[i][0] = dp[i-1][0]+data[i][0]-----------------------------------------第1列邊界

3. dp[i][i] = dp[i-1][i-1]+data[i];-------------------------------------------對角線邊界

4. dp[i][j] = MIN(dp[i-1][j-1],dp[i-1][j]) +data[i][j]----------------------其它正常情況(存在兩個指向的)

dt5.jpg

舉例分析

我們按照上面的圖例莲绰，從頂部到最底部，找一條最短路徑姑丑。在頂部時(shí),dp[0][0] = 2,來到第二層蛤签，首先數(shù)字3是第一列邊界，只能從數(shù)字2到達(dá)栅哀，所以dp[1][0]=5,數(shù)字4是對角線的邊界震肮，只能是對角線過來的，dp[1][1]=6,來到了第三層留拾，首先數(shù)字6戳晌，dp[2][0]=11,接下來數(shù)字5，它的前驅(qū)是兩個路痴柔，數(shù)字3沦偎，或者數(shù)字4過來的，我們查是最3和4對應(yīng)的dp值，發(fā)現(xiàn)數(shù)字3的dp更小豪嚎，所以我們選擇數(shù)字3那條路搔驼，數(shù)字5的dp就是dp[1][0]+5=10,接下來數(shù)字7又是對角線，邊界問題侈询，直接加上上一層dp,dp[2][2]=13.后面的就是這個規(guī)律舌涨。到了最底部，結(jié)束扔字。

代碼

    //三角形最短路徑
    void minPath()
    {
        int i, j, high,**data,**dp,**pre,min,index,num;
        printf_s("輸入三角形的高度: ");
        scanf_s("%d", &high);
        data = (int **)malloc(sizeof(int *)*high);
        dp = (int **)malloc(sizeof(int *)*high);
        pre = (int **)malloc(sizeof(int *)*high);
        //輸入三角形(二維數(shù)組里)
        for (i = 0; i < high; i++)
        {
            data[i] = (int *)malloc(sizeof(int) * high);
            dp[i] = (int *)malloc(sizeof(int) * high);
            pre[i] = (int *)malloc(sizeof(int) * high);
            for (j = 0; j <= i;j++)
            {
                scanf_s("%d", &data[i][j]);
            }
        }
        
        //初始化邊界問題
        dp[0][0] = data[0][0];
        pre[0][0] = -1;
        for (i = 1; i < high; i++)
        {
            dp[i][i] = dp[i - 1][i - 1] + data[i][i];
            dp[i][0] = dp[i - 1][0] + data[i][0];
            pre[i][i] = i-1;
            pre[i][0] = 0;
        }
        //其它正常情況
        for (i = 1; i < high; i++)
        {
            for (j = 1; j < high; j++)
            {
                if (i != j &&j != 0)
                {
                    if (dp[i - 1][j - 1] > dp[i - 1][j])
                    {
                        dp[i][j] = dp[i - 1][j] + data[i][j];
                        pre[i][j] = j;
                    }
                    else {
                        dp[i][j] = dp[i - 1][j-1] + data[i][j];
                        pre[i][j] = j-1;
                    }
                }
            }
        }
        //找出最短距離
        min = dp[high - 1][0];
        index = 0;
        for (i = 1; i < high; i++)
        {
            if (dp[high-1][i] < min)
            {
                min = dp[high-1][i];
                index = i;
            }
        }
        printf_s("最短距離是:%d它的路徑是: ",min);
        num = high-1;
        while (num!=0)
        {
            printf("%d ",data[num][index]);
            index = pre[num][index];
            num--;  
        }
        printf_s("%d\n", data[0][0]);
    }

問題5：最長遞增子序列

問題描述

給定一個無序的整數(shù)序列數(shù)組泼菌，求其中最長遞增子序列的長度，例如a[]={2,1,5,3,6,4,8,9,7}n=9,這個數(shù)組的最長遞增子序列就是{1,3,4,8,9}長度是5啦租。

求解思路

首先我們知道每一個單獨(dú)的數(shù)字哗伯，就可認(rèn)為它是遞增的，我么還是設(shè)計(jì)dp數(shù)組篷角，對應(yīng)下標(biāo)的dp表示當(dāng)前位置最長子序列長度焊刹。首先是邊界問題，每個單獨(dú)的數(shù)字都是視為遞增的恳蹲，dp[i] = 1(初始情況),然后我們繼續(xù)設(shè)立轉(zhuǎn)移方程虐块，dp[i] = max(dp[i],dp[j]+1),其中0<j<i;讓j從0開始一直遍歷到i的前一個位置，只要j對應(yīng)的數(shù)字小于i對應(yīng)的數(shù)字嘉蕾，我們就去判斷dp[j]+1贺奠，和dp[j]誰大，誰大dp[i]就等于這個數(shù)错忱±苈剩可能說的模糊，我會舉例子的,先把dP方程列出來以清。

1. dp[i] = 1,------------------------------------------0<i<n
2. dp[i] = max(dp[i],dp[j]+1)----------------------0<j<i(只要data[i]>data[j])

舉例分析

數(shù)列就是上面的a[] = {2,1,5,3,6,4,8,9,7} 長度是9

1. 我們首先是數(shù)字2儿普，直接dp[0]=1,因?yàn)樗堑谝粋€，不用判斷掷倔、
2. 接著是數(shù)字1眉孩，直接dp[1]=1,從第一個數(shù)字一直判斷到它前一個，它前面只有2勒葱，且小于這個數(shù)浪汪，退出。
3. 接著是數(shù)字5凛虽，直接dp[2]=1,從第一個數(shù)字一直判斷到它前一個死遭，首先是數(shù)字2，它大于數(shù)字2涩维，所以進(jìn)行比較dp[2]和dp[0]+1,此處的加一很好理解殃姓，5大于2袁波，所以在2對應(yīng)的遞增子序列長度加上1，去表示5的遞增子序列長度蜗侈，因?yàn)閐p[0]+1大于當(dāng)前的dp[2],更新dp[2]=dp[0]+1就是2,繼續(xù)來到數(shù)字1篷牌，它還是大于數(shù)字1，繼續(xù)比較dp[2]和dp[1]+1,此時(shí)等于dp[1]+1,所以不修改dp[2]值踏幻，繼續(xù)枷颊，發(fā)現(xiàn)遍歷結(jié)束，退出该面。
4. 接著是數(shù)字3夭苗，直接dp[3] = 1，
   • 3>2,dp[0]+1>dp[3],更新dp[3]=2
   • 3>1,dp[1]+1=dp[3],不更新
   • 3<5,不更新
5. 接著是數(shù)字6隔缀，直接dp[4]=1,
   • 6>2,dp[0]+1>dp[4],更新dp[4]=2,
   • 6>1,dp[1]+1=dp[4],不更新
   • 6>5,dp[2]+1>dp[4],更新dp[4]=3,
   • 6>3,dp[3]+1=dp[4],不更新
6. 题造。。猾瘸。界赔。。牵触。淮悼。。依次類推

代碼

//最長遞增子序列
void maxLen()
{
    int len, *data,i,j,*dp,max;
    printf_s("輸入你的數(shù)組長度: ");
    scanf_s("%d", &len);
    data = (int *)malloc(sizeof(int) * len);
    dp = (int *)malloc(sizeof(int) * len);
    for (i = 0; i < len; i++)
    {
        scanf_s("%d", &data[i]);
    }
    for (i = 0; i < len; i++)
    {
        dp[i] = 1;
        for (j = 0; j < i; j++)
        {
            if (data[j] < data[i])
            {
                if (dp[j] + 1 > dp[i])
                {
                    dp[i] = dp[j] + 1;
                }
            }
        }
    }
    max = dp[0];
    //找出最大長度
    for (i = 1; i < len; i++)
    {
        if (dp[i] > max)
        {
            max = dp[i];
        }
    }
    printf_s("%d", max);
}

問題6：0-1背包

問題描述

前面已經(jīng)多次出現(xiàn)了0-1背包問題揽思，關(guān)于描述我就簡單說下袜腥，給你一個有容量的背包，現(xiàn)在有n個物品钉汗，每個物品對應(yīng)不同的價(jià)值羹令，現(xiàn)在要求你裝入不同的物品，要求在不超過背包容量前提下儡湾，要求背包裝入物品的價(jià)值最大特恬。

假設(shè)我們給定背包的最大容量W=10，現(xiàn)在給你5個物品徐钠。它們的重量數(shù)組是w={2,2,6,5,4},它們的價(jià)值數(shù)組是v={6,3,5,4,6}。

求解思路

我們還是按照動態(tài)規(guī)劃的設(shè)計(jì)步驟役首，設(shè)計(jì)二維數(shù)組dp[i][j],其中這個dp[i][j]表示在已經(jīng)考慮了物品1尝丐，2，3衡奥，爹袁，i時(shí)，背包容量為j的情況下矮固，背包的最大價(jià)值失息。

那么我們可以試著列出邊界和轉(zhuǎn)移方程組

1. dp[i][0] = 0(背包容量為0譬淳，任何物品都不能裝入,價(jià)值就是0)
2. dp[0][i] = value(背包現(xiàn)在裝入物品0，value視情況盹兢，如果物品0可以放入邻梆，value=v[0],如果不能，value就是0)
3. dp[i][j] = dp[i-1][j] (物品i放不下了)
4. dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]] +v[i]) (在放入物品i和不放入物品i里面選擇最優(yōu)解)

此方程中的前三條容易理解绎秒，其中第二條就是初始物品0作為邊界浦妄。第四條比較抽象，其中第四條的規(guī)則時(shí)见芹，目前背包可以放入第i個物品剂娄，現(xiàn)在要你選擇放還是不放這個物品，這時(shí)候肯定有人要問玄呛，肯定放啊阅懦，為什么要這么沙雕一步驟？能放進(jìn)去徘铝，價(jià)值不是更大故黑？那么你的問題是很好的，我前幾次理解也是這么理解的庭砍，后來寫了一遍dp展開式场晶，明白了此處的放是這么個意思，dp[i][j]本質(zhì)是我在對第i個物品進(jìn)行抉擇時(shí)怠缸，有j容量的背包诗轻，此時(shí)背包里面什么也沒放，現(xiàn)在就是讓你選擇揭北，你是拿這j容量的背包去裝第0到i-1之間物品的最優(yōu)價(jià)值還是拿它去裝第i個物品加上剩余容量可以裝入的物品的最優(yōu)值扳炬，此時(shí)我們不清楚，因此此處要比較一番搔体，如果感覺我沒說明白恨樟，你可以繼續(xù)看下面的例子(dp展開式)

示例分析

• dp[0][0]=0，dp[0][1]=0,dp[0][2]=6,因?yàn)楸嘲藭r(shí)的容量是2,0是第一件物品疚俱，就是邊界劝术，直接放入。dp[0][3] = 6,dp[0][4]=6......dp[0][10]=6.s
• dp[1][0]=0,dp[1][1]=0,dp[1][2]=max(dp[0][2],dp[0][0]+v[1])=6就是在選擇物品1和不選擇之間挑選價(jià)值最大的就是6.后面的依次類推呆奕。
• 下面就是完整的dp數(shù)組

代碼

//0-1背包
void package()
{
    int w[] = { 2,2,6,5,4 };
    int v[] = { 6,3,5,4,6 };
    int len = 5, maxWeight = 10,i,j,weight;//dp數(shù)組存儲結(jié)果
    int dp[MAX][MAX];
    weight = maxWeight;//weight存儲當(dāng)前背包剩余容量
    for (i = 0; i < len; i++)
    {
        dp[i][0] = 0;
    }
    for (i = 0; i <= weight; i++)
    {
        if (w[0] <= i)
        {
            dp[0][i] = v[0];
        }
        else
        {
            dp[0][i] = 0;
        }
    }
    
    for (i = 1; i < len; i++)
    {
        for (j = 0; j <= weight; j++)
        {
            //是否可以放下第i個物品
            if (j >= w[i])
            {
                if (dp[i - 1][j] > dp[i - 1][j - w[i]] + v[i])
                {
                    dp[i][j] = dp[i - 1][j];
                }
                else
                {
                    dp[i][j] = dp[i - 1][j - w[i]] + v[i];
                }
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    printf_s("最大價(jià)值%d\n",dp[4][10]);
    //逆序推導(dǎo)選擇的物品
    len--;
    while (len > 0)
    {
        if (dp[len][weight] != dp[len - 1][weight])//選擇物品len
        {
            printf_s("物品%d被選中\(zhòng)n", len+1);
            weight -= w[len];
        }
        len--;
    }
            if(weight!=0)
            {
                  printf_s("物品%d被選中\(zhòng)n", len+1);
            }
}

問題7：完全背包

問題描述
完全背包是0-1背包的升級版养晋，和0-1背包題目一摸一樣，就是在0-1背包基礎(chǔ)上梁钾，添加一條規(guī)則绳泉，每個物品可以被選擇多次。現(xiàn)在我們假設(shè)有三件物品n=3,物品對應(yīng)的重量和價(jià)值分別是weight={3,4,2} ,value={4,5,3},背包的容量是7姆泻，求背包裝載的最大價(jià)值(每個物品可以被選擇多次)

求解思路

既然它是由0-1背包進(jìn)化的零酪，那么它也和0-1背包的狀態(tài)轉(zhuǎn)移方程基本一樣冒嫡。此時(shí)我們?nèi)匀辉O(shè)立dp[i][j]表示選擇第i個物品時(shí)，背包容量是j的情況下的最大價(jià)值四苇，然后考慮邊界孝凌，還是當(dāng)背包容量是0時(shí)，價(jià)值是0蛔琅，dp[i][0]=0,接著繼續(xù)初始化邊界胎许，以第一個物品作為邊界，dp[0][j],在容量j不同情況下罗售，dp[0][j]也是不同的辜窑。下表就是對邊界物品1的初始情況。

dp轉(zhuǎn)移方程如下

• dp[i][0]=0------------------------------------------背包無法裝入
• dp[0][i]=value--------------------------------------上面表格
• dp[i][j]=MAX(dp[i-1][j-w[i]k] +v[i]k)-------------在裝入與不裝選擇(物品i可以放入寨躁，必須滿足k*w[i]<=j)

對于轉(zhuǎn)移方程1和2都可以理解穆碎，有人可能疑惑，方程3咋在0-1背包基礎(chǔ)上大變啊职恳，你分析的對所禀，因?yàn)槲疫€沒說k是什么(我的錯),k就是這個方程的關(guān)鍵，它就是物品i選擇了幾件放钦，它從0開始一直遞增到背包裝不下的臨界值色徘，那么不裝入物品i如何在方程中體現(xiàn)？當(dāng)k取0值時(shí)操禀，表示裝入0件物品i褂策，化簡就是dp[i][j]=dp[i-1][j],是不是又和0-1背包的不裝物品i的轉(zhuǎn)移方程一樣了。下面表格是完整的dp數(shù)組

//完全背包
void full_Pack()
{
    int weight[] = {3, 4, 2};
    int value[] = { 4,5,3 };
    int len = 3, maxWeight = 7;
    int dp[MAX][MAX],i,j,k,max,count[MAX][MAX];
    //初始化邊界
    for (i = 0; i < len; i++)
    {
        dp[i][0] = 0;
    }
    for (i = 0; i <= maxWeight; i++)
    {
        for (k = 0; k*weight[0] <= i; k++)//背包容量足夠颓屑，放入物品0越多斤寂，價(jià)值越大。
        {
            dp[0][i] = k*value[0];
            count[0][i] = k;
        }
    }
    //開始
    for (i = 1; i < len; i++)
    {
        for (j = 1; j <= maxWeight; j++)
        {
            max = dp[i][0];
            dp[i][j] = max;
            count[i][j] = 0;
            for (k = 0; k*weight[i] <= j; k++)
            {
                if (dp[i - 1][j - weight[i] * k] + value[i] * k > max)
                {
                    max = dp[i - 1][j - weight[i] * k] + value[i] * k;
                    dp[i][j] = max;
                    count[i][j] = k;
                }
            }
        }
    }
    printf_s("最大價(jià)值: %d\n", dp[2][7]);
    //輸出選擇物品
    len--;
    while (len >= 0)
    {
        printf_s("%d %d\n", len + 1, count[len][maxWeight]);
        maxWeight -= weight[len] * count[len][maxWeight];
        len--;
    }
}

動態(tài)規(guī)劃的空間優(yōu)化：滾動數(shù)組

此處我們在淺談滾動數(shù)組揪惦，首先我們得知道滾動數(shù)組是什么遍搞？

在求解動態(tài)規(guī)劃問題中，我們常常會用規(guī)劃dp數(shù)組存放問題的解器腋，因?yàn)榇薲p數(shù)組不斷滾動刷新著溪猿，這時(shí)我們可對數(shù)組下標(biāo)特殊處理，讓每一次操作只使用若干個值蒂培，這種操作就是滾動數(shù)組再愈，目的就是為了壓縮空間。

此處我只舉一個簡單例子护戳，后面的大家可以自行拓展豐富。

我舉得例子就是我們上面將的第一個斐波那契數(shù)列垂睬，先觀察下它的動態(tài)規(guī)劃寫法代碼媳荒。

//改造前的
int Fib(int n)
{
    int dp[100] = {0};
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= n; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

此處我申請的是100個空間大小的數(shù)組抗悍，實(shí)際我們通常申請大小所求數(shù)列n大小的空間，那么我再通過改造代碼钳枕，你可以觀察下滾動數(shù)組的奇妙之處缴渊。

//改造后的
int Fib(int n)
{
    int dp[3];
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= n; i++)
    {
        dp[i % 3] = dp[(i - 2) % 3] + dp[(i - 1) % 3];
    }
    return dp[n % 3];
}

此時(shí)你會發(fā)現(xiàn)，僅僅用到了3個空間我們就完成了任意fib(n)的求法鱼炒，直接將空間復(fù)雜度由0(n)降低為o(1),是不是很牛逼啊衔沼。好了，我只是淺談滾動數(shù)組昔瞧，關(guān)于它如何構(gòu)造指蚁，如何更好設(shè)計(jì)，還需大家一起努力探索自晰。

獲取完整代碼

我分別用C凝化，C++，JAVA三種主流語言編寫了完整代碼酬荞，請大家指導(dǎo)批正搓劫，一起學(xué)習(xí)。

點(diǎn)擊查看