01背包問題

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

• 聲明一個數(shù)組f[n][c]的二維數(shù)組，f[i][j]表示在面對第i件物品，且背包容量為j時所能獲得的最大價值。
• 根據(jù)題目要求進行打表查找相關的邊界和規(guī)律
• 根據(jù)打表列寫相關的狀態(tài)轉移方程
• 用程序實現(xiàn)狀態(tài)轉移方程

真題演練：

       一個旅行者有一個最多能裝M公斤的背包，現(xiàn)在有n件物品，它們的重量分別是W1、W2、W3、W4、…、Wn。它們的價值分別是C1、C3、C2、…、Cn,求旅行者能獲得最大價值。

輸入描述：

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

輸出描述：

       僅一行，一個數(shù)，表示最大總價值

樣例：

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

解題步驟

定義一個數(shù)組dp[i][j]表示容量為j時，拿第i個物品時所能獲取的最大價值。

按照題目要求進行打表，列出對應的dp表。

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

如果單簽背包的容量可以裝下物品:
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表和我們的預期是相符合的！但是并沒有結束，動態(tài)規(guī)劃有一個后無效性原則(當前狀態(tài)只與前一個狀態(tài)有關)。那么我們就可以對dp數(shù)組進行壓縮處理，將二維數(shù)組轉換成一維數(shù)組。每一次選擇物品對這個數(shù)組進行更新就可以啦！那么就可以將狀態(tài)轉移方程壓縮成為 dp[j]=max(dp[j],dp[j-w[i]]+v[i]) 。不過我們需要注意的是在壓縮過后我們需要逆序刷新數(shù)組的值，如果正序刷新的話就不能保存上一個階段對應獲取最大價值的值了。那么我們就可以寫出以下程序：

#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表并沒有什么區(qū)別！

完全背包問題

題目描述：

       設有n種物品，每種物品有一個重量及一個價值，但每種物品的數(shù)量都是無限的，有一個背包，最大載重量為m，今從n中物品中選取若干件（同一種物品可以多次選?。┦蛊滟|量小于等于m，而價值的和為最大。

輸入：

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

輸出：

       僅一行，一個數(shù)，表示最大總價值。

樣例：

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

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

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個商品
        }
    }
}

       通過代碼可以發(fā)現(xiàn)通過這種樸素的算法是需要三重循環(huán)的，好像對時間復雜度比較高。那么我們也借鑒01背包來對完全背包進行打表！

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

       根據(jù)狀態(tài)轉移方程應該很快就能寫出程序了吧！但是根據(jù)dp的后無效性原則，對動態(tài)規(guī)劃狀態(tài)轉移方程進行壓縮！壓縮過后就是dp[j]=max(dp[j],dp[j-w[i]]+v[i]) ，小伙伴們一看是不是和01背包的狀態(tài)轉移方程一模一樣?。〉堑莾蓚€有個重大的區(qū)別：01背包使用的是上一條的數(shù)據(jù)，所以需要逆序避免覆蓋之前的值，而完全背包是從當前更新后的數(shù)據(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[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表和我們推測的并沒有什么區(qū)別，程序正確！

多重背包問題

題目描述：

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

輸入：

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

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

輸出：

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

示例：

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

       與完全背包不同的是：完全背包每個物品的個數(shù)是無限的，而多重背包是每個物品只能拿指定的件數(shù)。那么最容易想到的方法就是把相同的物品分開，比如說有n個a物品，就將它分成a1 a2 a3 a4…an然后用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背包的狀態(tài)轉移方程，去增加第i個物品拿k個的循環(huán)
        }
    }
}

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

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

       用二進制的思想就是每一個箱子代表二進制對應的位數(shù)，那么210大于1024應該是可以滿足題目條件的。那么每個箱子放的蘋果分別是1,2,4,8,16,32，…488（1000-512）。需要一個蘋果拿第一箱，需要兩個蘋果拿第二項，需要三個蘋果拿一二箱。那么對于需要拿1000箱的問題本來要循環(huán)1000次，經(jīng)過優(yōu)化以后只用循環(huán)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背包的狀態(tài)轉移方程，去增加第i個物品拿k個的循環(huán)
        }
    }
}

動態(tài)規(guī)劃解題思路

       對于動態(tài)規(guī)劃問題我們一般的思路如下：

• 判斷是動態(tài)規(guī)劃的解題思路以后立馬定義一個數(shù)組，把數(shù)組對應的下標、對應的值想清楚。
• 然后根據(jù)題目意思找規(guī)律進行打表，找出初始狀態(tài)以及一些邊界條件。
• 根據(jù)打表的數(shù)據(jù)找出狀態(tài)轉移方程。
• 最后根據(jù)狀態(tài)轉移方程進行編寫程序。

到此這篇關于C語言動態(tài)規(guī)劃之背包問題詳解的文章就介紹到這了,更多相關C語言 背包內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論