1召调、前言
背包問(wèn)題是典型的動(dòng)態(tài)規(guī)劃問(wèn)題稿静，它有非常多的類型州刽，本文討論最常見(jiàn)的0-1背包問(wèn)題
0-1背包問(wèn)題描述：
有一個(gè)竊賊在偷竊一家商店時(shí)發(fā)現(xiàn)有n件物品，第i件物品價(jià)值為vi元勋眯，重量為wi婴梧，假設(shè)vi和wi都為整數(shù)下梢。他希望帶走的東西越值錢(qián)越好，但他的背包中之多只能裝下W磅的東西塞蹭，W為一整數(shù)孽江。他應(yīng)該帶走哪幾樣?xùn)|西？
2番电、問(wèn)題分析
動(dòng)態(tài)規(guī)劃問(wèn)題最重要的就是找出狀態(tài)方程竟坛，方程找錯(cuò)了，一定做不出來(lái)钧舌。
根據(jù)背包問(wèn)題描述担汤，第一印象肯定不是鋼條切割類型的，因?yàn)槿绻驯嘲殖蓛蓚€(gè)背包洼冻，并一定兩個(gè)背包都能裝滿崭歧，可能會(huì)千萬(wàn)浪費(fèi)，那么背包問(wèn)題是否可以采用 “數(shù)組最大連續(xù)子元素和”方式解題撞牢？
假定前n-1個(gè)物品率碾，小偷已經(jīng)選好放入背包，此時(shí)價(jià)值最大屋彪，到第n個(gè)物品時(shí)所宰，如果背包已有重量加上wn仍然不超重的話，那么前n個(gè)物品中畜挥，加上vn仔粥，即為價(jià)值最大。
如果超重呢蟹但，那么不添加n即可躯泰，價(jià)值依然為之前背包物品價(jià)值。
設(shè)設(shè)有n個(gè)物品华糖，背包的重量為w麦向，C[i][w]為最優(yōu)解為：
3、編碼
已有狀態(tài)方程客叉，如何編碼呢诵竭？
C[i][w]中i和w均為變量，那么至少需要使用兩次循環(huán)兼搏，逐個(gè)求出所有的C[i][w]卵慰。
/**
* 0 1背包問(wèn)題
* 此問(wèn)題滿足最優(yōu)子問(wèn)題結(jié)構(gòu)。
* 如果加上第i項(xiàng)的重量向族，不會(huì)超重呵燕，那么總體最大價(jià)值為value[i] + select[i-1][j-weight[i]]
* 如果加上第i項(xiàng)的重量超重了，那么總體最大價(jià)值為select[i-1][j]
*/
public static int pack(int[] value, int[] weight, int w){
int[][] select = new int[value.length][w+1];
for (int i = 1; i <= w; i++) {
select[0][i] = 0;
}
for (int i = 1; i < value.length; i++) {
select[i][0] = 0;
for (int j = 0; j <= w; j++) {
if (weight[i] <= j) {
if (value[i] + select[i-1][j-weight[i]] > select[i-1][j]) {
select[i][j] = value[i] + select[i-1][j-weight[i]];
}else {
select[i][j] = select[i-1][j];
}
}else {
select[i][j] = select[i-1][j];
}
}
}
return select[value.length-1][w];
}
上述代碼中件相，i代表物品再扭，j代表背包重量氧苍。為了求解最后結(jié)果，需要把從0遞增到w的所有C[i][w]都求解一次泛范。
ps：代碼已上傳至github让虐，歡迎探討
