01背包問(wèn)題

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

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

真題演練：

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

輸入描述：

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

輸出描述：

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

樣例：

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

解題步驟

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

按照題目要求進(jìn)行打表，列出對(duì)應(yīng)的dp表。

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

如果單簽背包的容量可以裝下物品:
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
如果當(dāng)前背包的容量裝不下該物品:
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])//如果當(dāng)前背包的容量大于商品的質(zhì)量
            {
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//判斷是否應(yīng)該拿下
            }
            else//大于背包的當(dāng)前容量
            {
                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]);
}

       通過(guò)運(yùn)行以上程序可以看到最終的輸出dp表和我們的預(yù)期是相符合的！但是并沒(méi)有結(jié)束，動(dòng)態(tài)規(guī)劃有一個(gè)后無(wú)效性原則(當(dāng)前狀態(tài)只與前一個(gè)狀態(tài)有關(guān))。那么我們就可以對(duì)dp數(shù)組進(jìn)行壓縮處理，將二維數(shù)組轉(zhuǎn)換成一維數(shù)組。每一次選擇物品對(duì)這個(gè)數(shù)組進(jìn)行更新就可以啦！那么就可以將狀態(tài)轉(zhuǎn)移方程壓縮成為 dp[j]=max(dp[j],dp[j-w[i]]+v[i]) 。不過(guò)我們需要注意的是在壓縮過(guò)后我們需要逆序刷新數(shù)組的值，如果正序刷新的話就不能保存上一個(gè)階段對(duì)應(yīng)獲取最大價(jià)值的值了。那么我們就可以寫出以下程序：

#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])//如果當(dāng)前背包的容量大于商品的質(zhì)量
            {
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);//判斷是否應(yīng)該拿下
            }
        }
        for(int k=0;k<=m;k++)
        {
            printf("%d ",dp[k]);
        }
        printf("\n");
    }
    printf("%d\n",dp[n][m]);
}

       可以看出和上面輸出的dp表并沒(méi)有什么區(qū)別！

完全背包問(wèn)題

題目描述：

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

輸入：

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

輸出：

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

樣例：

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

       與01背包問(wèn)題不同的是這不是每個(gè)物品選擇拿與不拿的問(wèn)題了，而是要選擇幾個(gè)該物品，最終選擇價(jià)值最大的。那么我們可以在01背包的問(wèn)題上繼續(xù)進(jìn)行思考這個(gè)問(wèn)題，01背包中我們知道了之前的狀態(tài)，那么我無(wú)非就是要判斷拿k個(gè)物品和不拿時(shí)進(jìn)行比較，如果價(jià)值比之前大就拿下。而每個(gè)種類的物品最多只能拿取j/w[i]個(gè)，再加一重循環(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]);//判斷是否應(yīng)該拿下k個(gè)商品
        }
    }
}

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

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

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

#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])//如果當(dāng)前背包的容量大于商品的質(zhì)量
            {
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);//判斷是否應(yīng)該拿下
            }
        }
        for(int k=0;k<=m;k++)
        {
            printf("%d ",dp[k]);
        }
        printf("\n");
    }
    printf("%d\n",dp[m]);
}

       通過(guò)以上代碼的輸出可以看出打印的dp表和我們推測(cè)的并沒(méi)有什么區(qū)別，程序正確！

多重背包問(wèn)題

題目描述：

       為了慶祝班級(jí)在校運(yùn)會(huì)上取得了全校第一名的好成績(jī)，班主任決定開(kāi)一場(chǎng)慶功會(huì)，為此撥款購(gòu)買獎(jiǎng)品犒勞運(yùn)動(dòng)員。期望撥款金額能夠購(gòu)買最大價(jià)值的獎(jiǎng)品，可以補(bǔ)充他們的精力和體力。

輸入：

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

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

輸出：

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

示例：

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

       與完全背包不同的是：完全背包每個(gè)物品的個(gè)數(shù)是無(wú)限的，而多重背包是每個(gè)物品只能拿指定的件數(shù)。那么最容易想到的方法就是把相同的物品分開(kāi)，比如說(shuō)有n個(gè)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)轉(zhuǎn)移方程，去增加第i個(gè)物品拿k個(gè)的循環(huán)
        }
    }
}

       通過(guò)以上的代碼可以看出當(dāng)s[i]特別大的時(shí)候那么就會(huì)消耗非常多的時(shí)間復(fù)雜度，那么肯定是有優(yōu)化的方法的！那么我們可以通過(guò)二進(jìn)制來(lái)對(duì)這個(gè)同一個(gè)物品應(yīng)該拿取幾個(gè)進(jìn)行優(yōu)化。我們可以通過(guò)以下問(wèn)題進(jìn)行研究：

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

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

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

       對(duì)于動(dòng)態(tài)規(guī)劃問(wèn)題我們一般的思路如下：

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

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

最新評(píng)論