演算法競賽入門——動態規劃-有解無憂

記憶化搜索與動態規劃

01背包問題

題目描述

有 N 件物品和一個容量是 V 的背包，每件物品只能使用一次，
第 i 件物品的體積是 vi，價值是 wi，
求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大，
輸出最大價值，

輸入格式

第一行兩個整數，N，V，用空格隔開，分別表示物品數量和背包容積，
接下來有 N 行，每行兩個整數 vi,wi，用空格隔開，分別表示第 i 件物品的體積和價值，

輸出格式

輸出一個整數，表示最大價值，

資料范圍

0<N,V≤1000
0<v_i,w_i≤1000

輸入樣例

4 5
1 2
2 4
3 4
4 5

輸出樣例

8

分析
首先考慮樸素做法，即列舉所有可能的情況，輸出其中價值最大的那一個
時間復雜度O(2ⁿ)

代碼如下

#include <iostream>
using namespace std;
const int N=1010;
int V[N],W[N];
int n,v;
int res;

void dfs(int k,int w,int m)  //k代表當前選的是第k+1個物品，w是當前的物品價值，m是剩余背包容量
{
	if(k==n)   //所有物品都選過一遍
	{
		res=max(res,w);
		return ;
	}
	if(m>=V[k])
	{
		dfs(k+1,w+W[k],m-V[k]);
		dfs(k+1,w,m);
	}
	else
	{
		dfs(k+1,w,m);
	}
}

int main()
{
	cin>>n>>v;
	for(int i=0;i<n;i++)
	{
		cin>>V[i]>>W[i];
	}
	dfs(0,0,v);
	cout<<res<<endl;
	
	return 0;
}

提交結果：Time Limit Exceeded
這種寫法的時間復雜度是指數級別的，當N=100的時候，最壞就需要O(2¹⁰⁰)的時間，而題目中N<=1000，接下來就需要考慮對這種暴力解法進行優化，

在上述搜索的程序中，有些中間程序是相同的，它們的結果是相同的，但在搜索的程序中，并不會記錄這些值，每次都需要重新計算，從這個層面，可以考慮記錄中間結果，對上述演算法進行優化，

優化后的代碼

#include <iostream>
#include <cstring>
using namespace std;

const int N=1010;
int V[N],W[N];
int dp[N][N]; 
int n,v;

int dfs(int i,int j)
{
	if(dp[i][j]>=0)
	{
		return dp[i][j];
	}
	int res;
	if(i==n)
	{
		res=0;
	}
	else if(j<V[i])
	{
		res=dfs(i+1,j);
	}
	else
	{
		res=max(dfs(i+1,j),dfs(i+1,j-V[i])+W[i]);
	}
	return dp[i][j]=res;
}

int main()
{
	cin>>n>>v;
	memset(dp,-1,sizeof(dp));
	for(int i=0;i<n;i++)
	{
		cin>>V[i]>>W[i];
	}
	cout<<dfs(0,v)<<endl;
	
	return 0;
}

提交結果：Accepted
時間復雜度：O(NV)
對于同樣的引數只會在第一次被呼叫時執行遞回部分，第二次之后都會直接回傳，這種方法被稱為記憶化搜索，
根據上面的演算法用到的記憶化陣列，記dp[i][j]為從前i個物品中選出總體積不超過j的物品時總價值的最大值，可得以下遞推式
d p [ 0 ] [ j ] = 0 dp[0][j]=0 dp[0][j]=0
d p [ i ] [ j ] = { d p [ i ? 1 ] [ j ] ， j < V [ i ] m a x ( d p [ i ? 1 ] [ j ] , d p [ i ? 1 ] [ j ? V [ i ] ] + W [ i ] ) ， j > = V [ i ] dp[i][j]=\left\{ \begin{aligned} &dp[i-1][j]， & j<V[i] \\ &max(dp[i-1][j],dp[i-1][j-V[i]]+W[i])，&j>=V[i] \end{aligned} \right. dp[i][j]={?dp[i?1][j]，max(dp[i?1][j],dp[i?1][j?V[i]]+W[i])，?j<V[i]j>=V[i]?

AC代碼

#include <iostream>
#include <cstring>
using namespace std;

const int N=1010;
int V[N],W[N];
int dp[N][N]; 
int n,v;

int main()
{
	cin>>n>>v;
	for(int i=1;i<=n;i++)
	{
		cin>>V[i]>>W[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=v;j++)
		{
			if(j<V[i]) dp[i][j]=dp[i-1][j];
			else       dp[i][j]=max(dp[i-1][j],dp[i-1][j-V[i]]+W[i]);
		}
	}
	cout<<dp[n][v]<<endl;
	
	return 0;
}

這個演算法的時間復雜度也是O(NV)，但是簡潔了很多，以這種方式一步步按順序求出問題的解的方法被稱作動態規劃法，
觀察上面的代碼發現，dp[i][j]的取值只與上一層（即第i-1行）的值有關，且j<V[i]時，dp[i][j]的值就與上一層的值相等，因此可以將二維陣列dp[][]改成一維的dp[]，這種方法稱為滾動陣列，

AC代碼

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

需要注意的是，使用滾動陣列時，j應該反過來回圈，即從后面向前面覆寫，且回圈的條件是j>=V[i]，這是因為j<V[i]時，dp[j]的值不變，如果j從V[i]開始回圈，前面的dp[j]的值會發生改變，當j的值較大的時候，前面dp[j]的取值會對后面dp[j]的值產生影響，而j從v開始回圈就可以避免這個錯誤，在使用滾動陣列的時候要注意這兩個變化，滾動陣列的好處是可以節省空間，從二維陣列優化為一維，但時間復雜度不變，由于j<V[i]的時候不需要回圈，理論上運行時間比二維的做法短，

裝箱問題

題目描述
有一個箱子容量為V（正整數，0 ≤ V ≤ 20000），同時有n個物品（0＜n ≤ 30），每個物品有一個體積（正整數），
要求n個物品中，任取若干個裝入箱內，使箱子的剩余空間為最小，

輸入描述:

1個整數，表示箱子容量
1個整數，表示有n個物品
接下來n行，分別表示這n個物品的各自體積

輸出描述：

1個整數，表示箱子剩余空間，

示例1

輸入

24
6
8
3
12
7
9
7

輸出

0

分析

可以看作是簡化的01背包問題，將物品的體積看作價值，求出最大的價值，再用總體積減去最大的價值，可求得箱子剩余空間的最小值，首先可以考慮采用記憶化搜索的方法，采用記憶化搜索的方法注意進行初始化，可以初始化為-1，而不能是0，因為f[i][j]==0時，無法確定當前狀態的最大價值是0，還是沒有搜索過，

#include <bits/stdc++.h>

using namespace std;

const int N=35;
int v,n;

int a[N];
int f[N][20010];

int dfs(int i,int j)
{
	if(f[i][j]>=0) return f[i][j];
	if(i==n) return 0;
	int res;
	if(j<a[i]) return dfs(i+1,j);
	else return max(dfs(i+1,j),dfs(i+1,j-a[i])+a[i]);
	
	return f[i][j]=res;
}


int main()
{
	cin>>v>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	memset(f,-1,sizeof(f));
	cout<<v-dfs(0,v)<<endl;
	
	return 0;
}

還可以采用01背包狀態轉移那樣的方法做，將體積當做權值，陣列可以是二維的，也可以是一維的（滾動陣列），這兩種方法的核心代碼如下

二維陣列

 for(int i=1;i<=n;i++)
{
    for(int j=1;j<=v;j++)
    {
        if(j<a[i]) f[i][j]=f[i-1][j];
        else f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+a[i]);
    }
}

滾動陣列

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

此題還有另外一種思路，用bool陣列f[i][j]表示前i個物品能否放滿體積為j的背包，記錄最大的j，即為能放下的最大體積，再用容量減去最大體積，就可以得到空間的最小值，按照這個思路，仍有二維陣列和滾動陣列兩種做法，

二維陣列

#include <bits/stdc++.h>
using namespace std;
const int N=35;
int v,n;
int a[N];
bool f[N][20010];
int main()
{
	cin>>v>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	int ans=0;
    f[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=v;j++)
        {
        	if(j<a[i]) f[i][j]=f[i-1][j];
            else f[i][j]=f[i-1][j]||f[i-1][j-a[i]];
            if(f[i][j]) ans=max(ans,j);
        }
    }
    cout<<v-ans<<endl;
	
	return 0;
}

滾動陣列

#include <bits/stdc++.h>
using namespace std;
const int N=35;
int v,n;
int a[N];
bool f[20010];
int main()
{
	cin>>v>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	int ans=0;
    f[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=v;j>=a[i];j--)
        {
            if(!f[j]) f[j]=f[j-a[i]];
            if(f[j]) ans=max(ans,j);
        }
    }
    cout<<v-ans<<endl;
	
	return 0;
}

注意
f[0][0]或f[0]初值為1，體積為0的時候認為背包是放滿的，這樣設定保證j=a[i]時，f[i][j]可以賦值為1

滑雪

Description

Michael喜歡滑雪百這并不奇怪，因為滑雪的確很刺激，可是為了獲得速度，滑的區域必須向下傾斜，而且當你滑到坡底，你不得不再次走上坡或者等待升降機來載你，Michael想知道載一個區域中最長底滑坡，區域由一個二維陣列給出，陣列的每個數字代表點的高度，下面是一個例子

在這里插入圖片描述
一個人可以從某個點滑向上下左右相鄰四個點之一，當且僅當高度減小，在上面的例子中，一條可滑行的滑坡為24-17-16-1，當然25-24-23-…-3-2-1更長，事實上，這是最長的一條，

Input

輸入的第一行表示區域的行數R和列數C(1 <= R,C <= 100)，下面是R行，每行有C個整數，代表高度h，0<=h<=10000，

Output

輸出最長區域的長度，

Sample Input

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

Sample Output

25

分析
記憶化搜索，用f[i][j]表示從(i,j)滑下的最長路徑長度，對于每個點(i,j)能滑的最長長度與周圍四個點有關，f[i][j]的初始值為1，代表自身的長度為1，然后用(i,j)點的高度與周圍四個點的高度比較，狀態轉移方程如下，

F [ i ] [ j ] = m a x { f [ i ? 1 ] [ j ] + 1 if ( a [ i ? 1 ] [ j ] < a [ i ] [ j ] ) f [ i + 1 ] [ j ] + 1 if ( a [ i + 1 ] [ j ] < a [ i ] [ j ] ) f [ i ] [ j ? 1 ] + 1 if ( a [ i ] [ j ? 1 ] < a [ i ] [ j ] ) f [ i ] [ j + 1 ] + 1 if ( a [ i ] [ j + 1 ] < a [ i ] [ j ] ) F[i][j] = max\begin{cases} f[i - 1][j] + 1 &\text{if } (a[i - 1][j] <a[i][j]) \\ f[i + 1][j] + 1 &\text{if } (a[i + 1][j] <a[i][j]) \\ f[i][j - 1] + 1 &\text{if } (a[i][j - 1] <a[i][j]) \\ f[i][j + 1] + 1 &\text{if } (a[i][j + 1] <a[i][j]) \end{cases} F[i][j]=max??????????f[i?1][j]+1f[i+1][j]+1f[i][j?1]+1f[i][j+1]+1?if (a[i?1][j]<a[i][j])if (a[i+1][j]<a[i][j])if (a[i][j?1]<a[i][j])if (a[i][j+1]<a[i][j])?

AC代碼

#include <iostream>
#include <cstring>
using namespace std;

const int N=105;
int a[N][N];
int f[N][N];
int r,c;

int calc(int i,int j)
{
	if(f[i][j]!=0) return f[i][j];
	f[i][j]=1;
	if(a[i-1][j]<a[i][j]&&i-1>0) f[i][j]=max(f[i][j],calc(i-1,j)+1);
	if(a[i+1][j]<a[i][j]&&i+1<=r) f[i][j]=max(f[i][j],calc(i+1,j)+1);
	if(a[i][j-1]<a[i][j]&&j-1>0) f[i][j]=max(f[i][j],calc(i,j-1)+1);
	if(a[i][j+1]<a[i][j]&&j+1<=c) f[i][j]=max(f[i][j],calc(i,j+1)+1);
	return f[i][j];
}

int main()
{
	cin>>r>>c;
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=c;j++)
		{
			cin>>a[i][j];
		}
	}
	int ans=0;
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=c;j++)
			ans=max(ans,calc(i,j));
	}
	cout<<ans<<endl;
	
	return 0;
}

注意
如果(i,j)位于邊界要注意判斷四周的位置是否合法，而且最大值的位置不確定，要取所有位置上的最大值，此外本題沒有采用遞推的方式，即用兩重for回圈遍歷，而是采用記憶化搜索，這是因為每個點的取值與周圍四個點有關，而在01背包中每個點的取值只與上一層有關，因此此題適合用記憶化搜索，

總結

1.記憶化搜索和動態規劃從根本上來講就是一個東西，兩者的核心思想均為：利用對于相同引數答案相同的特性，對于相同的引數（回圈式的dp體現為陣列下標），記錄其答案，免去重復計算，從而起到優化時間復雜度的作用

2.做動態規劃的一般步驟：

第一步，結合原問題和子問題確定狀態
狀態的引數一般有
1）描述位置的：前(后)i單位，第i到第j單位，坐標為(i,j)，第i個之前（后）且必須
取第i個等
2）描述數量的：取i個，不超過i個，至少i個等
3）描述對后有影響的：狀態壓縮的，一些特殊的性質

第二步，確定轉移方程
1）檢查引數是否足夠；
2）分情況：最后一次操作的方式，取不取，怎么樣取——前一項是什么
3）初始邊界是什么
4）注意無后效性，比如說，求A就要求Ｂ，求Ｂ就要求Ｃ，而求Ｃ就要求Ａ，這就不符合無后效性了
根據狀態列舉最后一次決策（即當前狀態怎么來的）就可確定出狀態轉移方程！

第三步，考慮需不需優化

第四步，確定編程實作方式
1）遞推
2）記憶化搜索

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/253981.html

標籤：其他

上一篇：C語言實作掃雷

下一篇：掃雷游戲的C語言實作