前言
動态規劃算法的核心思想是:将大問題劃分為小問題進行解決，進而一步步擷取最優解的處理算法。
這樣一聽和分治算法有點相似啊。
是的，分治算法也是将大問題分為小問題，但是他們畢竟不同，不同之處在什麼地方呢?
分治算法是這樣的，本來有一個大問題，把他們呢分成10個獨立的小問題，每個問題都可以單獨執行。
而動态規劃是這樣子的，他一個問題分為10個小問題，解決一個問題需要上一個問題得出的結論，在原先問題解決得基礎上得到答案。
這個問題該怎麼求呢？
比如我們看電視有很多個頻道，我們會經常換台，如果頻道多了，那麼這時候選擇多就出現難選擇得問題了。
現在給我4Kg背包，如果給我1kg那麼該怎麼選呢？現在1kg給我
看下圖:
上面這個表格得意思是這樣得，比如x軸1磅y軸吉他，這個1500的意思是假如背包隻能裝1kg，隻能選吉他，那麼背包價格為1500。
x軸1磅y軸音響的時候，這個1500的意思是假如背包隻能裝1kg，隻能選吉他和音響，那麼背包價格為1500。其他類推。
那麼這些資料對這個4磅3個都可以選有什麼用？
看紅色這一塊:
這個資料有什麼用呢？假設我們4磅都裝不下新增可以裝的物品電腦，那麼可想而知，其實結果就是3000。
為什麼這麼判斷呢？假設裝不下電腦，那麼可以裝的物品數量沒變，而且背包大小沒變，那麼條件沒有任何改變自然結果不變。
這時候分析：
1.假如4磅的時候裝了3000的音響，那麼這時候加入這個可以選電腦條件，那麼是沒有任何效果，還是3000。
2.假如3磅的時候裝了一個電腦，那麼多出的一磅該怎麼選才最好呢？多出的一磅看下現在條件是啥？
現在的條件是背包1磅，有兩個物品可以選這時候可以查表啊，如下圖:
因為我們前面已經求出了背包1磅，有兩個物品可以選的最優解。
這時候就得出最優解。
正文
代碼如下:
int[] weight = {1,4,3 };
int[] val = {1500,3000,2000};
int m = 4;
int n = val.Length;
int[,] wv = new int[n+1,m+1];
//由于wv預設建立數組為0是以不必初始化第一行第一列為0
for (int i = 1; i <n+1; i++)
{
for (int j = 1; j < m + 1; j++)
{
//如果現在背包的品質裝不下新增物品的品質
if (weight[i - 1] > j)
{
wv[i, j] = wv[i - 1, j];
}
else
{
//如果可以裝下新增的商品,則嘗試新增商品，取最大值
wv[i, j] = Math.Max(wv[i-1,j],val[i-1]+wv[i-1,j-weight[i-1]]);
}
}
}
Console.WriteLine(wv[n,m]);
Console.Read();
結果為:
static void Main(string[] args)
{
//hanoiTower(5,'A','B','C');
int[] weight = {1,4,3 };
int[] val = {1500,3000,2000};
string[] names = {"吉他","音響","電腦" };
int m = 4;
int n = val.Length;
int[,] wv = new int[n+1,m+1];
int[,] path = new int[n+1,m+1];
//由于wv預設建立數組為0是以不必初始化第一行第一列為0
for (int i = 1; i <n+1; i++)
{
for (int j = 1; j < m + 1; j++)
{
//如果現在背包的品質裝不下新增物品的品質
if (weight[i - 1] > j)
{
wv[i, j] = wv[i - 1, j];
}
else
{
//如果可以裝下新增的商品,則嘗試新增商品，取最大值
if (val[i - 1] + wv[i - 1, j - weight[i - 1]] >= wv[i - 1, j])
{
wv[i, j] = val[i - 1] + wv[i - 1, j - weight[i - 1]];
path[i, j] = 1;
} else
{
wv[i, j] = wv[i - 1, j];
}
}
}
}
Console.WriteLine(wv[n,m]);
int a = n;
int b = m;
while (a > 0&&b>0)
{
if (path[a,b]==1)
{
Console.WriteLine("商品名字:"+names[a-1]+"重量:"+weight[a-1]+"價格:"+val[a-1]);
b -= weight[a - 1];
}
a--;
}
Console.Read();
}