動(dòng)態(tài)規(guī)劃(一)

1.01背包問題

1.1題目介紹

1.2思路一介紹(二維數(shù)組)

代碼如下：

#include<iostream>
#include<algorithm>
using namespace std;
 const int N=1010;
 int v[N],w[N]; //v[N]是物品體積 w[N]是物品的價(jià)值
 int f[N][N]; //f[i][j]在體積不超j的前提下，從i個(gè)物品中選擇最大值
 int main()
 {
     int n,m;
     cin>>n>>m;
     for(int i=1;i<=n;i++)
     {
         cin>>v[i]>>w[i];
     }
     for(int i=1;i<=n;i++)
     {
         for(int j=1;j<=m;j++)
         {
             f[i][j]=f[i-1][j];
             if(j>=v[i])//如果我們的背包容量j大于第i個(gè)物品的體積，我們?cè)谶M(jìn)行決策是否加入第i個(gè)物品
             f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
         }
     }
     cout<<f[n][m]<<endl;
     return 0;
 }

1.3思路二介紹(一維數(shù)組) 空間優(yōu)化

??為什么可以使用一維數(shù)組？

??我們先來看一看01背包問題的狀態(tài)轉(zhuǎn)移方程，我們可以發(fā)現(xiàn) f[i]只用到了f[i-1]，其他的是沒有用到的，我們可以用滾動(dòng)數(shù)組來做。
??還有一個(gè)原因就是我們?cè)谟?jì)算f[i] [j]的時(shí)候我們只用到了f[i-1] [j]和f[i-1] [j-v[i]]，其中j和j-v[i]都是小于等于j的，在j的同一側(cè)，所以我們綜合以上兩點(diǎn)原因就可以將二維優(yōu)化到一維，即完成空間優(yōu)化。

我們先來將二維和優(yōu)化后的一維在關(guān)鍵算法代碼上進(jìn)行一下對(duì)比：

for(int i = 1; i <= n; i++) 
    for(int j = m; j >= 0; j--)
    {
        if(j < v[i]) 
            f[i][j] = f[i - 1][j];  // 優(yōu)化前
            f[j] = f[j];            // 優(yōu)化后，該行自動(dòng)成立，可省略。
        else    
            f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);  // 優(yōu)化前
            f[j] = max(f[j], f[j - v[i]] + w[i]);                   // 優(yōu)化后
    }

實(shí)際上，只有當(dāng)枚舉的背包容量 >= v[i] 時(shí)才會(huì)更新狀態(tài)，因此我們可以修改循環(huán)終止條件進(jìn)一步優(yōu)化。

for(int i=1;j<=n;i++)
{
	for(int j=m;j>=v[i];j--)
	{
		f[j]=max(f[j],f[j-v[i]]+w[i]);
	}
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}

1.4思路三介紹(輸入數(shù)據(jù)優(yōu)化)

??我們注意到在處理數(shù)據(jù)時(shí)，我們是一個(gè)物品一個(gè)物品，一個(gè)一個(gè)體積的枚舉。因此我們可以不必開兩個(gè)數(shù)組記錄體積和價(jià)值，而是邊輸入邊處理。

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1005;
int f[MAXN];  // 

int main() 
{
    int n, m;   
    cin >> n >> m;

    for(int i = 1; i <= n; i++) {
        int v, w;
        cin >> v >> w;      // 邊輸入邊處理
        for(int j = m; j >= v; j--)
            f[j] = max(f[j], f[j - v] + w);
    }

    cout << f[m] << endl;

    return 0;
}

2.完全背包問題

2.1題目描述：

2.2思路一(樸素算法)

#include<iostream>
using namespace std;
const int N=1010;
int f[N][N];
int n,m;
int v[N],w[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k*v[i]<=j;k++)
            {
                f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

上述樸素算法和01背包問題的樸素算法非常相似，但是會(huì)超時(shí)。所以我們接下來就會(huì)對(duì)這個(gè)算法進(jìn)行優(yōu)化處理。

2.3思路二(將k優(yōu)化處理掉)

??我們先來分析一下狀態(tài)轉(zhuǎn)移方程，我們發(fā)現(xiàn)方程一和方程二有一定的聯(lián)系，我們先不看方程一紅色圈出來的部分，我們比較方程一黃色的部分和方程二的內(nèi)容，我們發(fā)現(xiàn)方程一就是比方程二每一項(xiàng)多了一個(gè)w，那么我們黃色圈出來的部分的最大值也就比方程二的最大值多w，那么我們其實(shí)就可以將方程一圈出來黃色的部分進(jìn)行等價(jià)替換，替換成紅色方框黃色字體的內(nèi)容，我們最終得出最下方的結(jié)論，其實(shí)我們要求得最大值之和兩個(gè)狀態(tài)有關(guān)，比較它們的最大值即可。

我們發(fā)現(xiàn)好像最后的狀態(tài)轉(zhuǎn)移方程和k并沒有關(guān)系了，那么我們就干脆去掉k的那次循環(huán)

所以我們對(duì)核心代碼進(jìn)行了優(yōu)化：

for(int i = 1 ; i <=n ;i++)
for(int j = 0 ; j <=m ;j++)
{
    f[i][j] = f[i-1][j];//狀態(tài)一，即不取第i個(gè)物品
    if(j-v[i]>=0)//判斷是否可以加入第i個(gè)物品
        f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);//狀態(tài)二
}

完整代碼如下：

#include<iostream>
using namespace std;
const int N=1010;
int f[N][N];
int n,m;
int v[N],w[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            f[i][j]=f[i-1][j];
            if(j>=v[i])
            {
                f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

我們來比較一個(gè)完全背包的核心代碼和01背包核心代碼的區(qū)別:

//01背包問題核心優(yōu)化后代碼
for(int i=1;i<=n;i++)
{
	for(int j=m;j>=v[i];j--)
	{	f[i][j]=f[i-1][j];
		if(j>=v[i])
		{
			f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
		}
	}
}
//完全背包問題核心優(yōu)化后代碼
for(int i = 1 ; i <=n ;i++)
for(int j = 0 ; j <=m ;j++)
{
    f[i][j] = f[i-1][j];//狀態(tài)一，即不取第i個(gè)物品
    if(j-v[i]>=0)//判斷是否可以加入第i個(gè)物品
        f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);//狀態(tài)二
}

我們發(fā)現(xiàn)其實(shí)本質(zhì)也就是一句不同：注意i的下標(biāo)

??我們這個(gè)i的下標(biāo)是根據(jù)兩個(gè)不同的背包問題的狀態(tài)轉(zhuǎn)移方程得出來的，我們01背包問題因?yàn)橐褂玫趇-1層的數(shù)據(jù)，所以我們枚舉j的時(shí)候只能從后往前枚舉，這樣做是因?yàn)閖-v[i]小于j，那么f[j-v[i]]的數(shù)據(jù)就會(huì)被改，那么我們使用的數(shù)據(jù)其實(shí)就是第i層的數(shù)據(jù)了，不滿足狀態(tài)轉(zhuǎn)移方程，所以我們要從后往前枚舉，但是完全背包問題使用的就是第i層的數(shù)據(jù)，所以不存在從前往后枚舉就會(huì)在使用前數(shù)據(jù)就發(fā)生意外改變的這種情況，所以就在這個(gè)地方這兩個(gè)核心算法略有差別。

2.4思路三(優(yōu)化j的初始條件)

這個(gè)和01背包問題的優(yōu)化方法是一樣的，就不多贅述了。

核心代碼如下：

for(int i = 1 ; i<=n ;i++)
    for(int j = v[i] ; j<=m ;j++)//注意了，這里的j是從小到大枚舉，和01背包不一樣
    {
            f[j] = max(f[j],f[j-v[i]]+w[i]);
    }

完整代碼如下：

#include<iostream>
using namespace std;
const int N = 1010;
int f[N];
int v[N],w[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 1 ; i <= n ;i ++)
    {
        cin>>v[i]>>w[i];
    }

    for(int i = 1 ; i<=n ;i++)
    for(int j = v[i] ; j<=m ;j++)
    {
            f[j] = max(f[j],f[j-v[i]]+w[i]);
    }
    cout<<f[m]<<endl;
}

總結(jié)

??本篇博客主要涉及動(dòng)態(tài)規(guī)劃背包問題的01背包問題和完全背包問題，給大家分享了實(shí)現(xiàn)的思路和代碼模板，大家也可以看看yxc的背包九講，圖片轉(zhuǎn)載于yxc，希望對(duì)大家有所幫助，后面會(huì)持續(xù)更新~文章來源地址http://www.zghlxwxcb.cn/news/detail-784422.html

到了這里，關(guān)于算法競(jìng)賽必考算法——?jiǎng)討B(tài)規(guī)劃(01背包和完全背包）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！