01背包问题
1问题描述
给定一个载重量为m，
个物品，其重量为wi，价值为vi，1i
，要求把物品装入背包，并使包内物品价值最大
2问题分析
在01背包问题中，物体或者被装入背包，或者不被装入背包，只有两种选择。循环变量i，j意义：前i个物品能够装入载重量为j的背包中
1m1数组value意义：valueij表示前i个物品能装入载重量为j的背包中物品的最大价值若wij，第i个物品不装入背包否则，若wij且第i个物品装入背包后的价值valuei1j，则记录当前最大价值（替换为第i个物品装入背包后的价值）计算最大价值的动态规划算法如下：
计算fori1irowiforj1jcoljwij第i个物品不装入背包valueijvaluei1jwij且第i个物品装入背包后的价值valuei1j则记录当前最大价值i
ttempvaluei1jwivi
fifwijtempvalueijvalueijtemp
即该段程序完成以下
个阶段：1：只装入1个物品，确定在各种不同载重量的背包下，能够得到的最大价值2：装入2个物品，确定在各种不同载重量的背包下，能够得到的最大价值。。。
：以此类推，装入
个物品，确定在各种不同载重量的背包下，能够得到的最大价值
3问题求解
确定装入背包的具体物品，从value
m向前逆推：若value
mvalue
1m，则第
个物品被装入背包，且前
1个物品被装入载重量为mw
的背包中否则，第
个物品没有装入背包，且前
1个物品被装入载重量为m的背包中以此类推，直到确定第一个物品是否被装入背包为止。逆推代码如下：
逆推求装入的物品jmforirow1i0iifvalueijvaluei1jci1jwi
4代码如下
f输入数据及输出数据均在文件中。输入数据格式：
mw1w2w
v1v2v
输出数据格式：maxValueicou
ti表示物品编号，cou
t表示该物品被选中次数
01背包问题求解visualstudio2005给定一个载重量为m及
个物品其重量为wi价值为vi1i
要求把物品装入背包并使包内物品价值最大i
cludestdiohi
cludestdlibhi
cludestri
ghdefi
eFILENAMELENGTH100classCBeibaopublici
tm_
Numberi
tm_
MaxWeighti
tm_pWeighti
tm_pValuei
tm_pCou
ti
tm_
MaxValue物品数量最大载重量每个物品的重量每个物品的价值每个物品被选中的次数最大价值
fpublicCBeibaoco
stcharfile
ameCBeibaoi
tGetMaxValuei
tGetMaxValuei
t
i
tmi
twi
tvi
tcvoidDisplayi
t
MaxVr