問題描述：
給定n種物品和一背包。物品i的重量是wi部默，其價值為vi，背包的容量為C造虎。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?
對于一種物品纷闺，要么裝入背包算凿，要么不裝。所以對于一種物品的裝入狀態(tài)可以取0和1.我們設(shè)物品i的裝入狀態(tài)為xi,xi∈ (0,1)犁功，此問題稱為0-1背包問題氓轰。
過程分析
數(shù)據(jù)：
物品個數(shù)n=5
物品重量w[n]={0，2浸卦，2署鸡，6，5限嫌，4}
物品價值V[n]={0靴庆，6，3怒医，5炉抒，4，6}
總重量c=10
（第0位稚叹，置為0焰薄，不參與計算，只是便于與后面的下標(biāo)進(jìn)行統(tǒng)一扒袖，無特別用處塞茅，也可不這么處理。）
背包的最大容量為10季率，那么在設(shè)置數(shù)組m大小時野瘦，可以設(shè)行列值為6和11，那么蚀同，對于m(i,j)就表示可選物品為i…n背包容量為j(總重量)時背包中所放物品的最大價值缅刽。
感覺動態(tài)規(guī)劃問題的核心還是在于在已有解決方案的基礎(chǔ)上優(yōu)化，背包問題兩點是構(gòu)建二維數(shù)組和通過數(shù)組尋找最優(yōu)解蠢络。
構(gòu)建的核心在于比較尋找最大值衰猛。如下圖所示，核心就是理解Max的尋找過程
還原最優(yōu)解的時候呢刹孔，則是根據(jù)構(gòu)造思路的一個逆向思考啡省。
ppt均來源與頂部博文
public class test03232137 {
public static int m[][]=new int[6][11];
public static int c=10;//背包容量
public static int[] w={0,2,2,6,5,4};//物品重量
public static int[] v={0,6,3,5,4,6};//物品對應(yīng)的價值
public static int n=5;//n為物品的個數(shù)
public static int[] x=new int[n+1];
public void package_1(int m[][],int w[],int v[],int n)//n代表物品的個數(shù)
{
//采用從底到頂?shù)捻樞騺碓O(shè)置m[i][j]的值
//首先放w[n]
for(int j = 0; j <= c; j++)
if(j < w[n]) m[n][j] = 0; //j小于w[n],所對應(yīng)的值設(shè)為0娜睛，否則就為可以放置
else m[n][j] = v[n];
//對剩下的n-1個物品進(jìn)行放置。
int i;
for(i = n-1; i >= 1; i--)
for(int j = 0; j <= c; j++)
if(j < w[i])
m[i][j] = m[i+1][j];//如果j < w[i]則卦睹，當(dāng)前位置就不能放置畦戒，它等于上一個位置的值。
//否則结序，就比較到底是放置之后的值大障斋，還是不放置的值大，選擇其中較大者徐鹤。
else m[i][j] = m[i+1][j] > m[i+1][j-w[i]] + v[i]?
m[i+1][j] : m[i+1][j-w[i]] + v[i];
}
public void answer(int m[][],int n)
{
int j = c;
int i;
for(i = 1; i <= n-1; i++)
if(m[i][j] == m[i+1][j])
x[i] = 0;
else{
x[i] = 1;
j = j - w[i];
}
x[n] = (m[i][j]==m[i-1][j]) ? 1 : 0;
}
public static void main(String[] args){
test03232137 t=new test03232137();
t.package_1(m,w,v,n);
for(int i = 0; i <= 5; i++)
{
for(int j = 0; j <= 10; j++)
System.out.print(" "+m[i][j]+" ");
System.out.println();
}
t.answer(m,n);
System.out.print("The best answer is:");
for(int i = 1; i <= 5; i++)
System.out.print(" "+x[i]+" ");
}
}
運行結(jié)果如圖
