參考：https://blog.csdn.net/xp731574722/article/details/70766804
價值數(shù)組v = {8, 10, 6, 3, 7, 2}，
重量數(shù)組w = {4, 6, 2, 2, 5, 1}检柬，
背包容量C = 12時對應的m[i][j]數(shù)組遵湖。
0 ????1 ????2 ????3???? 4???? 5???? 6 ????7 ????8???? 9 ????10???? 11???? 12
1???? 0 ????0 ????0 ????8 ????8 ????8 ????8 ????8 ????8 ????8 ????????8 ????8
2 ? ? 0 ?????0 ????0 ????8 ????8 ? ?10 ?10 ????10 10 ????18 ????18 ????18
3 ????0 ????6 ????6 ????8 ????8 ????14 ????14 ????16 16 ????18 ????18???? 24
4 ????0 ????6???? 6 ????9 ????9???? 14 ????14 ????17 17 ????19 ????????19 24
5???? 0 ????6 ????6 ????9 ????9 ????14 ????14 ????17 17 ????19 ????21 ????24
6 ????2 ????6 ????8 ????9 ????11 ????14???? 16 ????17 19 ????19 ????21 ????24
(第一行和第一列為序號蒋搜，其數(shù)值為0)
如m[2][6],在面對第二件物品宪萄，背包容量為6時我們可以選擇不拿皿曲，那么獲得價值僅為第一件物品的價值8蔬将，如果拿匕累，就要把第一件物品拿出來，放第二件物品迂求，價值10碾盐，那我們當然是選擇拿。m[2][6]=m[1][0]+10=0+10=10;依次類推揩局，得到m[6][12]就是考慮所有物品廓旬，背包容量為C時的最大價值。
給定 n 種物品和一個容量為 C 的背包谐腰，物品 i 的重量是 wi，其價值為 vi?
? ? int v[N]={0,8,10,6,3,7,2};
? ? int w[N]={0,4,6,2,2,5,1};
? ? int m[N][N]; ? ? ? ? ? ? ? ?//表示背包的價值涩盾，第i個物品時背包的重量j包含多少的價值
? ? int n=6,c=12; ? ? ? ? ? ?//n是數(shù)量十气，c是重量
? ? memset(m,0,sizeof(m));
? ? for(int i=1;i<=n;i++) ? ?
//動態(tài)規(guī)劃：子問題的解能夠從前面找到（中國大學Mooc屈婉玲動態(tài)規(guī)劃算法視頻:https://www.icourse163.org/learn/PKU-1002525003? tid=1002695005#/learn/content?type=detail&id=1003850904&sm=1）因此數(shù)量從1開始增長，計算包含第一個物品時的最大價值
? ? {
? ? ? ? for(int j=1;j<=c;j++)
? ? ? ? {
? ? ? ? ? ? if(j>=w[i])
? ? ? ? ? ? ? ? m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]); ? ?//能夠放的下看拿上是否會獲得更大價值春霍，j-w[i]為了給第i個物品騰空砸西，然后加上它的價值，相同的空間裝的i-1個物品是否比裝第i個物品更劃得來
? ? ? ? ? ? else
? ? ? ? ? ? ? ? m[i][j]=m[i-1][j]; ? ? //因為放不下了，所以第i個物品與第I-1個物品的價值相等
? ? ? ? }
? ? }
到這一步芹枷，可以確定的是可能獲得的最大價值衅疙，但是我們并不清楚具體選擇哪幾樣物品能獲得最大價值。
另起一個 x[ ] 數(shù)組鸳慈，x[i]=0表示不拿饱溢，x[i]=1表示拿。
m[n][c]為最優(yōu)值走芋，如果m[n][c]=m[n-1][c] ,說明有沒有第n件物品都一樣绩郎，則x[n]=0 ; 否則 x[n]=1。當x[n]=0時翁逞，由x[n-1][c]繼續(xù)構造最優(yōu)解肋杖；當x[n]=1時，則由x[n-1][c-w[i]]繼續(xù)構造最優(yōu)解挖函。以此類推状植，可構造出所有的最優(yōu)解。（這段全抄算法書怨喘，實在不知道咋解釋啊津畸。。）
追蹤解：
void traceback()
{
? ? for(int i=n;i>1;i--)
? ? {
? ? ? ? if(m[i][c]==m[i-1][c])
? ? ? ? ? ? x[i]=0;
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? x[i]=1;
? ? ? ? ? ? c-=w[i];
? ? ? ? }
? ? }
? ? x[1]=(m[1][c]>0)?1:0;
}
---------------------
作者：青龍指引你
來源：CSDN
原文：https://blog.csdn.net/xp731574722/article/details/70766804
版權聲明：本文為博主原創(chuàng)文章哲思，轉載請附上博文鏈接洼畅！
