淺談動态規劃（01背包問題）

一、 背景：可能許多人認為動态規劃這種東西是特别進階的算法，于是心中把這種算法捧上了天，心中對動态規劃産生忌憚。這篇文章晚上閑着沒事幹，單純依靠自己頭腦記憶敲出來的。不夾雜書中枯燥無味的原理。

二、 動态規劃概叙：動态規劃又叫做 “填表法”，所謂 ”填表“ 就是表面意思，給你一個表來填。程式設計角度上講就是給二維數組指派（此處二維隻是個例子，并不是所有的表都是二維）。表就是記錄過程的一張備忘錄。

三、 動态規劃原理：動态規劃同貪心法和分治法有點相似，就是得找出最優子結構，進而求得問題的最優解。講籠統一點就是，把問題分解（分治法）成子問題，再從子問題中找出子問題的最優解，然後構成問題的最優解。其他的不多說了，多說也無益。

四 、 子問題：01背包的子問題就是一件物品對重量的影響。

此處n=4，W=7

五 、 例子：說那麼多也無用，我認為想學習動态規劃就必須得多做有關動态規劃的題，因為在動态規劃中，不同的定義會有不同的解法。（比如：就01背包來說，求的是最大價值，定義可以是針隊不同重量，求最大價值。還有就是，針隊不同價值，求最少重量）看到了把，這兩種定義，具體應用得看問題的規模。（這裡不詳細說，想參加什麼競賽的可以了解一下）。

下面給出這兩種定義的代碼。

這裡補充一下：不知道怎麼求狀态轉移方程的可以先1、暴力遞歸——2、帶自頂向下備忘錄的遞歸——3、自底向下的動态規劃。備忘錄和動态規劃複雜度是一樣的，隻是求解時順序不一樣而已。（有的書說備忘錄有備援）

（1）針隊不同重量，求最大價值。（這也是很多算法書的例子）

#include <iostream>
#include <algorithm>

using namespace std;

#define MAX_N 100

int n = 4;
int W = 5;
int w[MAX_N] = { 2,1,3,2 };
int v[MAX_N] = { 3,2,4,2 };
int dp[MAX_N + 1][MAX_N + 1];//記憶化數組
void solve()
{
	for(int i = 0; i < n; i++)
		for (int j = 0; j <= W; j++)
		{
			if (j < w[i])
				dp[i + 1][j] = dp[i][j];
			else
				dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
		}
	cout << dp[n][W];
}
void main()
{
	memset(dp, 0, sizeof(dp));
	solve();
}
           

（2）針隊不同價值求最少重量

#include<iostream>
#include<algorithm>

using namespace std;

#define MAX_N 100
#define MAX_V 10000
#define INF 999999
typedef long long ll;
int n = 4;
int w[MAX_N] = { 2,1,3,2 };
int v[MAX_N] = { 3,2,4,2 };
ll W = 5;
int dp[MAX_N + 1][MAX_V*MAX_N + 1];

void solve()
{
	fill(dp[0], dp[0] + MAX_N*MAX_V + 1, INF);//把數組所有元素設維無窮大
	dp[0][0] = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= MAX_N*MAX_V; j++)//j是最大價值
		{
			if (j < v[i])
				dp[i + 1][j] = dp[i][j];
			else
				dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i]);//針隊不同價值計算最少重量
		}
	int res = 0;
	for (int j = 0; j < MAX_N*MAX_V; j++)
		if (dp[n][j] <= W) res = j;//價值
	cout << res;
}

void main()
{
	solve();
}
           

好了，想要了解更多，可以在評論下方留言。