C語言動態規劃——背包問題詳解

作為一名大三老學長，我的嵌入式春招找實習之旅好像接近尾聲了，春招投遞了BAT、美團、華為、oppo、大疆等公司的實習，大多數公司都給了面試機會，尤其是阿里，筆試一道編程題都沒有寫出來居然還給了面試機會！還是非常感謝這些互聯網公司能夠給我面試機會的，oppo 的HR面后半個多月了也沒有訊息，華為投遞一個月也沒有什么進展，目前已經拿到了大疆、CVTE實習，打算5月去深圳大疆實習！
盡管已經拿到了實習的機會，但是通過春招發現了很多的知識空白需要填補，畢竟生于憂患，死于安樂嘛，筆試了很多家公司，編程題總結起來就是字串、動態規劃、二叉樹、圖、BFS、DFS，一個搞嵌入式的為什么要整這么難的筆試題？八成是因為內卷吧！所以為了秋招，把該補的知識還是得趕快補上，該刷的題還是得刷起來！

往期推薦：

看完這些面試必問的Linux小知識，我保證你面試后會來給我的文章一鍵三連
經過筆試和多輪技術面試我居然敗給了HR面？

01背包問題

給定n種物品，和一個容量為C的背包，物品i的重量是w[i],其價值為v[i]，問如何選擇裝入背包的物品，使得裝入背包中的總價值最大？（面對每個武平，只能有選擇拿取或者不拿兩種選擇，不能選擇裝入某物品的一部分，也不能裝入物品多次）

• 宣告一個陣列f[n][c]的二維陣列，f[i][j]表示在面對第i件物品，且背包容量為j時所能獲得的最大價值，
• 根據題目要求進行打表查找相關的邊界和規律
• 根據打表列寫相關的狀態轉移方程
• 用程式實作狀態轉移方程

真題演練：

一個旅行者有一個最多能裝M公斤的背包，現在有n件物品，它們的重量分別是W₁、W₂、W₃、W₄、…、W_n，它們的價值分別是C₁、C₃、C₂、…、C_n,求旅行者能獲得最大價值，

輸入描述：

第一行：兩個整數，M（背包容量，M<= 200)和N（物品數量，N<=30);
第2…N+1行：每行兩個整數W_i，C_i，表示每個物品的質量與價值，

輸出描述：

僅一行，一個數，表示最大總價值

樣例：

輸入：
    10 4
    2 1
    3 3
    4 5
    7 9
輸出：
    12

解題步驟

1. 定義一個陣列dp[i][j]表示容量為j時，拿第i個物品時所能獲取的最大價值，
2. 按照題目要求進行打表，列出對應的dp表，

對于一個動態規劃問題設定下標時最好從0開始，因為動態規劃經常會和上一個狀態有關系！從上面的dp表可以看出來對于一個物品我們拿還是不難需要進行兩步來判斷，第一步：判斷背包當前的容量j是否大于物品當前的質量，如果物品的質量大于背包的容量那么就舍棄，第二步：如果背包可以裝下這個物品，就需要判斷裝下該物品獲取的最大價值是不是大于不裝下這個物品所獲取的最大價值，如果大于那么就把東西裝下！根據這樣的思想我們可以得到狀態轉移方程：

 如果單簽背包的容量可以裝下物品:
	dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
如果當前背包的容量裝不下該物品:
	dp[i][j]=dp[i-1][j];

#include <stdio.h>
int max(const int a,const int b)
{
    return a>b ? a:b;
}
int main()
{
    int w[35]={0},v[35]={0},dp[35][210]={0};
    int n,m;
    scanf("%d %d",&m,&n);
    int i,j;
    for(i=1;i<=n;i++){
        scanf("%d %d",&w[i],&v[i]);
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(j>=w[i])//如果當前背包的容量大于商品的質量
            {
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//判斷是否應該拿下
            }
            else//大于背包的當前容量
            {
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    for(int k=0;k<=n;k++)
    {
        for(int l=0;l<=m;l++)
        {
            printf("%d ",dp[k][l]);
        }
        printf("\n");
    }
    printf("%d\n",dp[n][m]);
}

通過運行以上程式可以看到最終的輸出dp表和我們的預期是相符合的！但是并沒有結束，動態規劃有一個后無效性原則(當前狀態只與前一個狀態有關)，那么我們就可以對dp陣列進行壓縮處理，將二維陣列轉換成一維陣列，每一次選擇物品對這個陣列進行更新就可以啦！那么就可以將狀態轉移方程壓縮成為 dp[j]=max(dp[j],dp[j-w[i]]+v[i]) ，不過我們需要注意的是在壓縮過后我們需要逆序重繪陣列的值，如果正序重繪的話就不能保存上一個階段對應獲取最大價值的值了，那么我們就可以寫出以下程式：

#include <stdio.h>
int max(const int a,const int b)
{
    return a>b ? a:b;
}
int main()
{
    int w[35]={0},v[35]={0},dp[210]={0};
    int n,m;
    scanf("%d %d",&m,&n);
    int i,j;
    for(i=1;i<=n;i++){
        scanf("%d %d",&w[i],&v[i]);
    }
    for(i=1;i<=n;i++){
        for(j=m;j>=0;j--){
            if(j>=w[i])//如果當前背包的容量大于商品的質量
            {
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);//判斷是否應該拿下
            }
        }
        for(int k=0;k<=m;k++)
        {
            printf("%d ",dp[k]);
        }
        printf("\n");
    }
    printf("%d\n",dp[n][m]);
}

可以看出和上面輸出的dp表并沒有什么區別！

完全背包問題

題目描述：

設有n種物品，每種物品有一個重量及一個價值，但每種物品的數量都是無限的，有一個背包，最大載重量為m，今從n中物品中選取若干件（同一種物品可以多次選取）使其質量小于等于m，而價值的和為最大，

輸入：

第一行：兩個整數，M（背包容量，M<= 200)和N（物品數量，N<=30);
第2…N+1行：每行兩個整數W_i，C_i，表示每個物品的質量與價值，

輸出：

僅一行，一個數，表示最大總價值，

樣例：

輸入:
10 4
2 1
3 3
4 5
7 9
輸出:
12

與01背包問題不同的是這不是每個物品選擇拿與不拿的問題了，而是要選擇幾個該物品，最終選擇價值最大的，那么我們可以在01背包的問題上繼續進行思考這個問題，01背包中我們知道了之前的狀態，那么我無非就是要判斷拿k個物品和不拿時進行比較，如果價值比之前大就拿下，而每個種類的物品最多只能拿取j/w[i]個，再加一重回圈不就可以啦！程式的核心代碼如下：

for(i=1;i<=n;i++){
    for(j=m;j>=0;j--){
        for(k=0;k<=j/w[i];k++)
        {
            dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);//判斷是否應該拿下k個商品
        }
    }
}

通過代碼可以發現通過這種樸素的演算法是需要三重回圈的，好像對時間復雜度比較高，那么我們也借鑒01背包來對完全背包進行打表！

根據表中紅色標記的數值來看，需要注意的是如果背包的容量不能裝下當前物品的質量，那么當前容量所能裝下價值最大的物品就等于上一個物品所能保存的最大價值，重點看一下4是怎么來的，這個4并不是從 i-1來的，而是從i來的，通過正序推出該物品的價值，狀態轉移方程就可以寫成是 ：dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]) 和01背包的唯一區別是max的第二個引數，01背包是i-1，而完全背包是i，而且是通過正序推理得到的狀態轉移方程，

根據狀態轉移方程應該很快就能寫出程式了吧！但是根據dp的后無效性原則，對動態規劃狀態轉移方程進行壓縮！壓縮過后就是dp[j]=max(dp[j],dp[j-w[i]]+v[i]) ，小伙伴們一看是不是和01背包的狀態轉移方程一模一樣啊！但是但是兩個有個重大的區別：01背包使用的是上一條的資料，所以需要逆序避免覆寫之前的值，而完全背包是從當前更新后的資料進行相關的操作的 ，通過以上分析我們可以寫出如下程式：

#include <stdio.h>
int max(const int a,const int b)
{
    return a>b ? a:b;
}
int main()
{
    int w[35]={0},v[35]={0},dp[210]={0};
    int n,m;
    scanf("%d %d",&m,&n);
    int i,j;
    for(i=1;i<=n;i++){
        scanf("%d %d",&w[i],&v[i]);
    }
    for(i=1;i<=n;i++){
        for(j=0;j<=m;j++){
            if(j>=w[i])//如果當前背包的容量大于商品的質量
            {
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);//判斷是否應該拿下
            }
        }
        for(int k=0;k<=m;k++)
        {
            printf("%d ",dp[k]);
        }
        printf("\n");
    }
    printf("%d\n",dp[m]);
}

通過以上代碼的輸出可以看出列印的dp表和我們推測的并沒有什么區別，程式正確！

多重背包問題

題目描述：

為了慶祝班級在校運會上取得了全校第一名的好成績，班主任決定開一場慶功會，為此撥款購買獎品犒勞運動員，期望撥款金額能夠購買最大價值的獎品，可以補充他們的精力和體力，

輸入：

第一行輸入兩個數n（n<=500),m(m<=6000)，其中n代表希望購買的獎品的種數，m表示撥款金額，

接下來的n行，每行3個數,w,v,s分別表示第i種獎品的價格、價值（價格與價值是不同的概念）和能購買的最大數量（買0件到s件均可），其中w<=100,v<=1000,s<=10;

輸出：

一行：一個數，表示此次購買能獲得的最大價值（注意！不是價格），

示例：

輸入：
5 1000
輸出：
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1

與完全背包不同的是：完全背包每個物品的個數是無限的，而多重背包是每個物品只能拿指定的件數，那么最容易想到的方法就是把相同的物品分開，比如說有n個a物品，就將它分成a₁ a₂ a₃ a₄…a_n然后用01背包的方法去解決，那么我們就可以寫出以下核心代碼：

for(i=1;i<=n;i++){
    for(j=m;j>=0;j--){
        for(k=0;k<=s[i]&&j>=k*w[i];k++)
        {
            dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);//從01背包的狀態轉移方程，去增加第i個物品拿k個的回圈
        }
    }
}

通過以上的代碼可以看出當s[i]特別大的時候那么就會消耗非常多的時間復雜度，那么肯定是有優化的方法的！那么我們可以通過二進制來對這個同一個物品應該拿取幾個進行優化，我們可以通過以下問題進行研究：

有1000個蘋果，10個箱子怎么放，不管我想拿多少個蘋果，都可以成箱成箱的拿？

用二進制的思想就是每一個箱子代表二進制對應的位數，那么2¹⁰大于1024應該是可以滿足題目條件的，那么每個箱子放的蘋果分別是1,2,4,8,16,32，…488（1000-512），需要一個蘋果拿第一箱，需要兩個蘋果拿第二項，需要三個蘋果拿一二箱，那么對于需要拿1000箱的問題本來要回圈1000次，經過優化以后只用回圈10次就可以啦！那么我們就可以寫出以下程式啦！

for(i=1;i<=n;i++){
    for(j=m;j>=0;j--){
        for(k=0;k<=s[i]&&j>=k*w[i];k<<=1)
        {
        	if((k<<1)>s[i]&&j>=k*w[i])
        	{
        		dp[j]=max(dp[j],dp[j-(s[i]-k)*w[i]]+(s[i]-k)*v[i]);
        	}
            else
            	dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);//從01背包的狀態轉移方程，去增加第i個物品拿k個的回圈
        }
    }
}

動態規劃解題思路

對于動態規劃問題我們一般的思路如下：

• 判斷是動態規劃的解題思路以后立馬定義一個陣列，把陣列對應的下標、對應的值想清楚，
• 然后根據題目意思找規律進行打表，找出初始狀態以及一些邊界條件，
• 根據打表的資料找出狀態轉移方程，
• 最后根據狀態轉移方程進行撰寫程式，

不積小流無以成江河，不積跬步無以至千里，而我想要成為萬里羊，就必須堅持學習來獲取更多知識，用知識來改變命運，用博客見證成長，用行動證明我在努力，
如果我的博客對你有幫助、如果你喜歡我的博客內容，記得“點贊” “評論” “收藏”一鍵三連哦！聽說點贊的人運氣不會太差，每一天都會元氣滿滿呦！如果實在要白嫖的話，那祝你開心每一天，歡迎常來我博客看看，