动态规划及回溯法解决01背包问题.doc

0-1背包动向规划解决问题
一、问题描绘：
n个物品，它们有各自的重量和价值，现有给定容量的背包，怎样让背包里装入的物品拥有最大的价值总和？
二、总体思路：
根据动向规划解题步骤（问题抽象化、成立模型、寻找拘束条法。
编写版word
首先要明确这张表是至底向上，从左到右生成的。
序号
Weight
Value
1
2
3
4
5
6
7
1
3
9
4
7
11
13
16
20
20
2
5
10
4
7
11
11
11
14
17
3
2
7
4
7
11
11
11
11
11
4
1
4
4
4
4
4
4
4
4
从表格中能够看出背包的最大价值
value=20，即当
X1=1，X2=0，X3=1，X4=1。
五、算法测试代码：
#include<>
#include<>
#include<iostream>
#include<queue>
#include<climits>
#include<cstring>
usingnamespacestd;
constintc=8;//背包的容量
constintw[]={0,3,5,2,1};//物品的重量，其中0号地点不使用。
constintv[]={0,9,10,7,4};//物品对应的待加，0号地点置为空。
constintn=sizeof(w)/sizeof(w[0])-1;//n为物品的个数
intx[n+1];
voidpackage0_1(intm[][11],constintw[],constintv[],constintn)//n代表物品的个数
{
编写版word
//采用从底到顶的次序来设置m[i][j]的值
//首先放w[n]
for(intj=0;j<=c;j++)
if(j<w[n])m[n][j]=0;//j小于w[n],所对应的值设为0，否则就为能够放置
elsem[n][j]=v[n];
//对剩下的n-1个物品进行放置。
inti;
for(i=n-1;i>=1;i--)
for(intj=0;j<=c;j++)
if(j<w[i])
m[i][j]=m[i+1][j];//如果j<w[i]则，目前地点就不能放置，它等于上一个地点的值。//否
则，就比较到底是放置之后的值大，仍是不放置的值大，选择其中较大者。
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];
}
voidanswer(intm[][11],constintn)
{