? ? 動態(tài)規(guī)劃，Dynamic Programing（簡稱DP），個人認為是一種算法思想，用來解決多階段多層次的選擇問題，把一個復(fù)雜的問題分解成每個小塊的子問題然后一個個解決來找到最優(yōu)解。

? ? DP適用重疊子問題和最優(yōu)子結(jié)構(gòu)的性質(zhì)的問題。

? ? DP問題范圍分為線性與非線性。線性DP可以順推可以逆推，在理解過程我們可以嘗試畫出二維圖進行理解；非線性DP類似樹形圖，可以從根到葉，也可以從葉到根。

? ? 在學(xué)習(xí)DP的過程我們或多或少的會遇到背包問題，咱們這里就談?wù)?1背包的想法與思路吧。作者是大一新生，發(fā)表文章表達自己對于背包問題的看法，希望高手可以指出不足，感謝！話不多說進入正題......

01背包是最經(jīng)典的DP問題，為什么要學(xué)好01背包呢？是因為咱們很多題目是基于01背包的基礎(chǔ)進行做題的，前面也提到了DP是一種算法思想，不要過于拘束。背包問題大概就是給你一個容量為V的背包以及多個物品，每個物品對應(yīng)一個體積和其價值，這種題目咱們可以分成五個模塊：

1.理解題干含義定義dp[i]的含義

2.分析題干關(guān)鍵部分找到狀態(tài)轉(zhuǎn)移方程

3.dp數(shù)組的初始化如何設(shè)計

4.如何正確的遍歷dp數(shù)組

5.打印dp數(shù)組

上面的五個模塊是分析DP問題的步驟，下面我們通過題干來理解01背包的求法......

咱們按照五個模塊分析題干：

1.咱們分析如何定義dp數(shù)組的含義，在這里需要咱們細心閱讀題干，題干表明背包容量是固定的，如果超過背包容量是不就代表無法拿這個物品，所以背包容量是其限制條件，如果咱們假設(shè)i為枚舉到第i個物品，dp[i]代表當(dāng)前的最大金額，在這里咱們要想給其加入限制條件，是不是可以開辟一個二維數(shù)組，因為二維數(shù)組內(nèi)兩個參數(shù)可以代表兩個含義，所以設(shè)置dp[][]，其中舉個例子dp[i][j - w[i]]中i代表枚舉到第幾個物品，j - w[i]代表因為背包加入第i個物品導(dǎo)致背包空間剩下j - w[i]。

2.我們創(chuàng)建dp數(shù)組含義，接下來就該分析狀態(tài)轉(zhuǎn)移方程了。

? ? 最開始的情況是max(dp[1][i],dp[1][j - w[1]] + v[1]),因為我最開始拿第一個物品，他的選擇情況只能是要么選擇要么不選擇，dp[1][j]代表不選而dp[1][j - w[1]]代表選擇。注意一下這里是要最大金額，所以咱們要比較我是拿1才能使金額保持最大還是不拿1才能使金額最大，然后繼續(xù)篩選，可以寫出dp[i][j] = max(dp[i - 1][j],dp[i -? 1][j - w[i]] + v[i]),這個就是狀態(tài)轉(zhuǎn)移方程。dp[i - 1][j]代表不選而dp[i - 1][j - w[i]]代表選擇物品,其實個人認為核心思想就是去向問題，也就是將每個情況分別羅列出來來構(gòu)成狀態(tài)轉(zhuǎn)移方程，這道題就是將你選和不選兩種情況通過編程語言說明，然后要選出最大值，所以要在去向前加入max來保證選出的永遠是最大金額。

? ? 這是個遞推過程，你要明白如果你要是認為我怎么這樣拿就可以拿到最大值了，那你肯定是跟我一樣忘記了dp數(shù)組的含義，我們最開始dp數(shù)組設(shè)定的含義是要的是最大金額，也就是說在做DP，你要時刻記住不要忘記設(shè)置的dp數(shù)組本身的含義。個人理解這個想不明白就自己動手畫出二維圖，我的老師告訴我，你想不明白就自己把整個流程自己畫一遍hhh，然后我花了一個多小時才搞明白（哭）。

? ? 如果要是還是想不明白，請看我主頁內(nèi)對于二維背包圖的解釋吧，這里先不介紹了hhh....

3.初始化.對于初始化如何做呢？我個人認為就是單純的找邊界，為了不讓數(shù)組越界導(dǎo)致程序亂碼，我們可以通過自己設(shè)置的dp數(shù)組的定義結(jié)合題意來理解。在本題我們可以發(fā)現(xiàn)dp[0] 代表的含義是選到第0個物品其最大金額，那顯而易見dp[0] = 0。這道題初始化很簡單，但是初始化切記一點，這道題是要最大金額，那我為什么不能初始化為2,3,4....以及1e9呢？（思考），因為你要是取1e9為初始值，你覺得后面再跟dp[0]比較還能有比他大的數(shù)了嗎？哈哈哈哈，所以我們對于最大值問題可以設(shè)置<= 0 的數(shù)（思考）。

4.遍歷數(shù)組。咱們這里很多人包括我也不理解為啥很多博主講這些遍歷順序為啥都不一樣?。?，這里推薦都能看到這里的朋友告訴你，這個東西靠聽網(wǎng)課只能學(xué)到大概，但是細節(jié)需要自己理解，只有自己真正明白二維背包圖怎么畫才會真正初步會01背包的入門，我指的是含義，在二維做法其實大部分可以不需要考慮遍歷順序問題，不妨畫一下圖吧（如果你偷懶，來我主頁看吧hhh），畫完圖你就明白他遞推過程很有趣，跟dfs其實是不同的，但也不是完全不同。但是后期你要是學(xué)壓維的時候你就要重點看遍歷順序問題了，我就不介紹了（沒精力了抱歉）。

5.打印數(shù)組（看代碼吧碼不動了（哭））

#include <stdio.h>
const int N = 1000;
int w[N];//價值
int v[N];//重量
int f[N][N];//i表示遍歷到第幾個  j表示剩余容量
int max(int a,int b)
{
	int res = a > b ? a : b;
	return res;
}
int main()
{
	int n,m;//n表示幾個物品  m表示背包大小
	scanf("%d %d",&n,&m);
	for(int i = 1;i <= m;i++)
	{
		scanf("%d %d",&v[i],&w[i]);
	}
	for(int i = 1;i <= n;i++)//遍歷物品，可以調(diào)換方向的
	{
		for(int j = 0;j <= m;j++)//背包容量，可以調(diào)換方向的
		{
			if(j < v[i])//篩掉背包空間不夠的操作
			{
				f[i][j] = f[i - 1][j];
			}
			else
			{
				f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]] + w[i]);
			}
		}
	}
	printf("%d",f[n][m]);
	return 0;
}

看到這里喜歡各位能夠理解他的含義，然后看完希望你做一些有關(guān)01背包的改動題，然后后期我會根據(jù)自己學(xué)習(xí)的方向?qū)懸幌?strong>滾動數(shù)組（壓維）。好了好了，感謝觀看，希望點點關(guān)注，同時也希望大佬可以為我指點一下，個人是大一新生，對于算法路線些許迷茫，今天就到這里感謝觀看（愛心）。

看到這里給個好東西hhh......文章來源地址http://www.zghlxwxcb.cn/news/detail-776166.html

子問題的和: dfs(x) = dfs(x + 1) + dfs(x + 2);

最優(yōu)子問題: dfs(x) = max(dfs(x + 1),dfs(x + 2));

到了這里，關(guān)于動態(tài)規(guī)劃（DP）---- 01背包入門詳解----二維圖是學(xué)會的關(guān)鍵的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！