0-1背包问题：给出n种物品和容量为c的背包，物品I重量为wi，其价值为vi。
问：为了使放在背包里的东西的总价值最大，应该怎么选择放在背包里的东西？
分析一波，对于每一件物品，我们只有取与不取两种选择。 不能放某个物品的一部分，也不能多次放同一物品。
解决方案：声明大小为m[n][c]的二维数组m[ i ][ j ] 表示 在面对第 i 件物品，且背包容量为 j 时所能获得的最大价值，可以轻松分析m[i][j]的计算方法。
(1) .在j w[i]的情况下，此时背包的容量不足以放下第I项，只能选择没有
m[ i ][ j ]=m[ i-1 ][ j ]
)2).j=w[i]的情况下，此时背包的容量可以放下第I个物品，必须考虑拥有这个物品是否能得到更大的价值。
如果取的话，m[ i ][ j ]=m[ i-1 ][ j-w[ i ] ] v[ i ]。 这里，m[ i-1 ][ j-w[ i ] ]是指考虑i-1个物品，将背包的容量设为j-w[i]时的最大价值，相当于为第I个物品空出了w[i]的空间。
如果不取，则m[ i ][ j ]=m[ i-1 ][ j ]，同(1) )。
拿不拿，当然比较这两种情况，其价值最大。
由此，得到了状态转移方程。
if(j=w(I ) ) m ) ) j ) ) m ) I-1 )，m ) I-1 ) [j-w ) ] I ) )； else m[i][j]=m[i-1][j]；
例：0-1背包问题。 采用动态规划算法求解0-1背包问题时，采用二维数组m[i][j]取背包剩余容量为j，可选为I、i 1、…、n时0-1背包问题的最佳值。 绘制值数组v={8、10、6、3、7、2}，
重量排列w={4、6、2、2、5、1}，
与背包容量C=12时相对应的m[i][j]数组。
01234567891011210008882000881010183068183068141618244069141719191919191919，192450691414141414，12333
像m[2][6]，面对第二个物品，当背包容量为6时，我们可以选择不拿。 这样，获得价值只有第一件物品的价值8。 如果要取的话，取出第一个物品，放入第二个物品，价值10的话，我们当然选择取。 m[2][6]=m[1][0] 10=0 10=10； 依次得到m[6][12]是考虑到所有事物，将背包的容量设为c时的最大价值。
# include iostream # includecstringusingnamespacestd； 常数int n=15； int main () intv [ n ]={ 0，8，10，6，3，7，2 }； intw [ n ]={ 0，4，6，2，2，5，1 }； int m[N][N]； int n=6，c=12； 消息(m，0，sizeof(m ) m )； for(intI=1； i=n； I ) for(intj=1； j=c； j () if ) j=w[I] ) m[I] ) j ) ) max ) I-1 )，m[I-1][j-w[I] ) v[I] )； else m[i][j]=m[i-1][j]； }for(intI=1； i=n； I ) for(intj=1； j=c； j({coutm[I][j] '； } coutendl； }返回0； }
到了这个地步，得到的最大价值是肯定的，但不知道具体选择什么样的东西能得到最大的价值。
产生另一个x[ ]数组。 x[i]=0表示不取，x[i]=1表示取。
m[n][c]是最佳值，在m[n][c]=m[n-1][c]的情况下，如果有无第n个项目相同，则x[n]=0； 否则x[n]=1。 当x[n]=0时，继续由x[n-1][c]构造最优解； 当x[n]=1时，继续从x[n-1][c-w[i]]构造最优解。 这样，就可以构建所有的最优解。 (把这个算法的书全部抄下来，不知道该怎么解释。 ）
void跟踪back () { for } inti=n； i1； 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； }
示例：
某厂预计明年将有a、b、c、d四个新建项目，每个项目投资额Wk及其投资后利润Vk如下表所示，投资总额为30万元，如何选择项目才能实现总利润最大？
Project
Wk
Vk
a
15
12
B
10
8
C
12
9
d
8
5
前面两个代码# include iostream # includecstringusingnamespacestd； 常数int n=150； intv [ n ]={ 0，12，8，9，5 }； intw [ n ]={ 0，15，10，12，8 }； int x[N]； int m[N][N]； int c=30； int n=4； void跟踪back () { for } inti=n； i1； 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； }int main () (memset ) m，0，sizeof(m ) )； for(intI=1； i=n； I ) for(intj=1； j=c； j () if ) j=w[I] ) m[I] ) j ) ) max ) I-1 )，m[I-1][j-w[I] ) v[I] )； else m[i][j]=m[i-1][j]； }/*for(intI=1； i=6； I ) for(intj=1； j=c； j({coutm[I][j] '； } coutendl； } * /跟踪后退(； for(intI=1； i=n； I ) coutx[i]； 返回0； }
输出x[i]数组： 0111，输出m[4][30]:22。
结论：选择卡介苗的3个项目总利润最大，为22万元。
但是，该算法只能得到一个最优解，并不能得到所有的最优解。