動(dòng)態(tài)規(guī)劃的經(jīng)典例子

2019-11-14 12:27:46

字體：大中小

供稿：網(wǎng)友

最長不減子序列收集最多的蘋果01背包問題問題描述問題分析代碼實(shí)現(xiàn)

最長不減子序列

一個(gè)序列有N個(gè)數(shù)：A[1],A[2],…,A[N]，求出最長非降子序列的長度。 (講DP基本都會(huì)講到的一個(gè)問題LIS：longest increasing subsequence)

正如上面我們講的，面對(duì)這樣一個(gè)問題，我們首先要定義一個(gè)“狀態(tài)”來代表它的子問題，并且找到它的解。注意，大部分情況下，某個(gè)狀態(tài)只與它前面出現(xiàn)的狀態(tài)有關(guān)，而獨(dú)立于后面的狀態(tài)。

5，3，4，8，6，7

根據(jù)上面找到的狀態(tài)，我們可以得到：（下文的最長非降子序列都用LIS表示）

前1個(gè)數(shù)的LIS長度d(1)=1(序列：5)前2個(gè)數(shù)的LIS長度d(2)=1(序列：3；3前面沒有比3小的)前3個(gè)數(shù)的LIS長度d(3)=2(序列：3，4；4前面有個(gè)比它小的3，所以d(3)=d(2)+1)前4個(gè)數(shù)的LIS長度d(4)=3(序列：3，4，8；8前面比它小的有3個(gè)數(shù)，所以 d(4)=max{d(1),d(2),d(3)}+1=3)

狀態(tài)轉(zhuǎn)換分成為：

d(i) = max{1, d(j)+1},其中j

#include <iostream>using namespace std;int lis(int A[], int n){ int *d = new int[n]; int len = 1; for(int i=0; i<n; ++i){ d[i] = 1; for(int j=0; j<i; ++j) if(A[j]<=A[i] && d[j]+1>d[i]) d[i] = d[j] + 1; if(d[i]>len) len = d[i]; } delete[] d; return len;}int main(){ int A[] = { 5, 3, 4, 8, 6, 7 }; cout<<lis(A, 6)<<endl; return 0;}

以上是O(n2 $n^2$ )的算法，還有O(nlogn)的實(shí)現(xiàn)如下：

//在非遞減序列 arr[s..e]（閉區(qū)間）上二分查找第一個(gè)大于等于key的位置，如果都小于key，就返回e+1int upper_bound(int arr[], int s, int e, int key){ int mid; if (arr[e] <= key) return e + 1; while (s < e) { mid = s + (e - s) / 2; if (arr[mid] <= key) s = mid + 1; else e = mid; } return s;}int LIS(int d[], int n){ int i = 0, len = 1, *end = (int *)alloca(sizeof(int) * (n + 1)); end[1] = d[0]; //初始化：長度為1的LIS末尾為d[0] for (i = 1; i < n; i++) { int pos = upper_bound(end, 1, len, d[i]); //找到插入位置 end[pos] = d[i]; if (len < pos) //按需要更新LIS長度 len = pos; } return len;}

參考：

http://www.hawstein.com/posts/dp-novice-to-advanced.html https://www.felix021.com/blog/read.php?1587

收集最多的蘋果

平面上有N*M個(gè)格子，每個(gè)格子中放著一定數(shù)量的蘋果。你從左上角的格子開始，每一步只能向下走或是向右走，每次走到一個(gè)格子上就把格子里的蘋果收集起來，這樣下去，你最多能收集到多少個(gè)蘋果。

解這個(gè)問題與解其它的DP問題幾乎沒有什么兩樣。第一步找到問題的“狀態(tài)”，第二步找到“狀態(tài)轉(zhuǎn)移方程”，然后基本上問題就解決了。

首先，我們要找到這個(gè)問題中的“狀態(tài)”是什么？我們必須注意到的一點(diǎn)是，到達(dá)一個(gè)格子的方式最多只有兩種：從左邊來的(除了第一列)和從上邊來的(除了第一行)。因此為了求出到達(dá)當(dāng)前格子后最多能收集到多少個(gè)蘋果，我們就要先去考察那些能到達(dá)當(dāng)前這個(gè)格子的格子，到達(dá)它們最多能收集到多少個(gè)蘋果。 (是不是有點(diǎn)繞，但這句話的本質(zhì)其實(shí)是DP的關(guān)鍵：欲求問題的解，先要去求子問題的解)

經(jīng)過上面的分析，很容易可以得出問題的狀態(tài)和狀態(tài)轉(zhuǎn)移方程。狀態(tài)S[i][j]表示我們走到(i, j)這個(gè)格子時(shí)，最多能收集到多少個(gè)蘋果。那么，狀態(tài)轉(zhuǎn)移方程如下：

s[i][j]=A[i][j]+max(S[i?1][j],if $s[i][j] = A[i][j] + max(S[i-1][j], if$ i > 0;S[i][j?1],if $; S[i][j-1], if$ j > 0) $)$

其中i代表行，j代表列，下標(biāo)均從0開始；A[i][j]代表格子(i, j)處的蘋果數(shù)量。

S[i][j]有兩種計(jì)算方式：1.對(duì)于每一行，從左向右計(jì)算，然后從上到下逐行處理；2. 對(duì)于每一列，從上到下計(jì)算，然后從左向右逐列處理。這樣做的目的是為了在計(jì)算S[i][j]時(shí)，S[i-1][j]和S[i][j-1]都已經(jīng)計(jì)算出來了。

偽代碼如下：

#include <iostream> using namespace std; #define MAX_N 100 #define MAX_M 100 int arr[ MAX_N ][ MAX_M ] = { 0 }; int dp[ MAX_N + 2 ][ MAX_M + 2 ] = { 0 }; int main(){ int n, m; cin>> n >> m; //輸入n*m的方格 int i, j ; for( i = 0; i < n; i++){ for( j = 0; j < m; j++) cin>> arr[ i ][ j ]; } //輸入方格中各個(gè)格子中的蘋果數(shù)量 for( i = 0; i < n; i++){ for( j = 0; j < m; j++){ dp[ i + 1 ][ j + 1 ] = dp[ i ][ j + 1] > dp[ i + 1 ][ j ] ? dp[ i ][ j + 1] + arr[ i ][ j ] : dp[ i + 1][ j ] + arr[ i ][ j ]; } } cout<<dp[i][j]<<endl; return 0; }

http://www.tuicool.com/articles/IVVvue

01背包問題

問題描述

有編號(hào)分別為a,b,c,d,e的五件物品，它們的重量分別是2,2,6,5,4，它們的價(jià)值分別是6,3,5,4,6，現(xiàn)在給你個(gè)承重為10的背包，如何讓背包里裝入的物品具有最大的價(jià)值總和？

問題分析

01背包的狀態(tài)轉(zhuǎn)換方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }

代碼實(shí)現(xiàn)

#include<stdio.h> #include<iostream> using namespace std; int table[10][100]={0}; int tableTwo[10][100]; int flag[10]={-1}; int Knapsack(int v[],int w[],int c,int n){//value weight capacity num for(int i=1;i<n+1;i++){//因?yàn)樯婕暗絠-1的計(jì)算，所以下標(biāo)從1開始 for(int j=1;j<c+1;j++){ if(j<w[i]){ table[i][j]=table[i-1][j]; //flag[i]=0; }else{ table[i][j]=max(table[i-1][j],table[i-1][j-w[i]]+v[i]); //flag[i]=table[i-1][j]>(table[i-1][j-w[i]]+v[i])?0:1; } } } return table[n][c]; } int KnapsackTwo(int v[],int w[],int c,int n){//此方法從n->1計(jì)算。自底向上，自左向右 int jMax=min(w[n]-1,c); for(int j=0;j<jMax;j++)tableTwo[n][j]=0;//j<當(dāng)前背包容量或者當(dāng)前物品重量時(shí)，tableTwo[n][j]=0; for(int j=w[n];j<=c;j++)tableTwo[n][j]=v[n];//當(dāng)前背包容量可以裝得下時(shí)， tableTwo[n][j]=v[n]; for(int i=n-1;i>1;i--){ jMax=min(w[i],c); for(int j=0;j<=jMax;j++)tableTwo[i][j]=tableTwo[i+1][j]; for(int j=w[i];j<=c;j++)tableTwo[i][j]=max(tableTwo[i+1][j],tableTwo[i+1][j-w[i]]+v[i]);//當(dāng)前背包容量裝得下，但是要判斷其價(jià)值是否最大，確定到底裝不裝 } tableTwo[1][c]=tableTwo[2][c];//先假設(shè)1物品不裝 if(c>=w[1])tableTwo[1][c]=max(tableTwo[1][c],tableTwo[2][c-w[1]]+v[1]);//根據(jù)價(jià)值，判斷到底裝不裝 return tableTwo[1][c];//返回最優(yōu)值 } void Traceback(int w[],int c,int n){//根據(jù)最優(yōu)值，求最優(yōu)解 for(int i=1;i<n;i++){ if(tableTwo[i][c]==tableTwo[i+1][c])flag[i]=0; else { flag[i]=1; c-=w[i]; } } flag[n]=tableTwo[n][c]?1:0; } int main(){ int weight[6]={0,2,2,6,5,4};//最低位補(bǔ)了0，從weight[1]開始賦值 int value[6]={0,6,3,5,4,6}; int c=10; cout<<"第一種方法->總價(jià)值最大為："<<Knapsack(value,weight,c,5)<<endl; cout<<"第二種方法->總價(jià)值最大為："<<KnapsackTwo(value,weight,c,5)<<endl; Traceback(weight,c,5); cout<<"最優(yōu)值的解："; for(int i=1;i<5+1;i++)cout<<flag[i]<<" "; cout<<endl; for(int i=1;i<6;i++){ for(int j=0;j<11;j++){ http://blog.csdn.net/catkint/article/details/51009680 http://blog.csdn.net/mu399/article/details/7722810