1 01背包问题
有N件物品和一个重量为c的背包。（每种物品均只有一件）第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使价值总和最大。
相关题目：http://acm.hdu.edu.cn/showproblem.php?pid=2602
2 分析
背包问题具有最优子结构，将在总重量不超过c的前提下，前n种物品的总价值所能达到的最高值定义为f(n, c)。
可以看出如果通过第n次选择得到的是一个最优解的话，那么第n-1次选择的结果一定也是一个最优解。这符合动态规划中最优子问题的性质。
在第n件物品放进容量v的背包时，它有两种情况
情况一: 第i件不放进去，这时所得价值为:f(n-1,c)
情况二: 第i件放进去，这时所得价值为：v[n]+f(n-1, c-w[n])
根据上面的分析，我们可以得到如下的递归式:
当w[n]>C时，f(n,C)=f(n-1,C);
当w[n]<=C时，f(n，C) = max(f(n-1,C), v[n]+f(n-1, C-w[n]) );
终止条件为： f(n,0),f(0,C),f(0,0) = 0;
用决策树分析如下，f(n,c),x 中x代表当前的最大值
最优解为f(n,C)中最大值，可以在求解过程中用一个数来存储最大值，其中存储f值的数组中的值可以抽象为对象（该对象包括2个属性：当前价值和，当前剩余的重量）。
画决策树时先构造一边直到叶子节点，然后再回溯
从决策树的叶子节点可以看出，最大价值为46
3 递归算法
public class PackageProblem{
//-----------------------------------------------------------------------
private int[] w; //物品重量数组
private int[] v; //物品价值数组
private int c; //背包容量
private int[] y; //解向量,y[i]=1表示选取物品，y[i]=0表示不选取物品
//-----------------------------------------------------------------------
public int f(int[] w,int[] v,int c){
//输入控制
if(w==null || v==null || c<=0)
return 0;
int wLength=w.length();
int vLength=v.length();
if(wLength!=vLength)
return 0;
else{ //初始化私有属性
n=wLength;
this.w=w;
this.v=v;
y=new int[n];
return f(n,c);
}//end else
}//end f()
//-----------------------------------------------------------------------
public int[] getY(){
return y;
}//end getY()
//-----------------------------------------------------------------------
//n为第n个待选物品
private int f(int n,int c){
//base case
if(n==0 || c=0) //当物品数量为0，最优解为0
return 0;
else{
for(int i=n-1;i>=0;i++){ //从最终目标出发，自顶向下求解。从当前所剩物品的最后一个物品开始向前，逐个判断是否要添加到背包中
//如果当前要判断的物品重量大于背包当前所剩的容量，那么就不选择这个物品，在这种情况的最优解为f(n-1,C)
if(w[i]>c){
y[i]=0;
return f(n-1,c);
}//end if
else{
//如果当前待判断的物品重量wi<C,那么就选取f(n-1,C)和vi+f(n-1,C-wi)中的最大值
int temp1=f(n-1,c); //不放入第n个物品
int temp2=f(n-1,c-w[i])+v[i]; //放入第n个物品
//返回选择物品i和不选择物品i中最优解大的一个
if(temp1>temp2){
y[i]=0; //这种情况下表示物品i未被选取
return temp1;
}//end if
else{
y[i]=1; //物品i被选取
return temp2;
}//end else
}//end else
}//end for
}//end else
}//end f
//-----------------------------------------------------------------------
public void test(){
int[] w={1,3,4,5};
int[] v={2,30,44,20};
int c=5;
PackageProblem pp=new PackageProblem();
int maxValue=pp.f(w,v,c);
System.out.println("max value="+maxVlaue);
//选取的物品
int [] y=pp.getY();
for(int i=0;i<w.length;i++){
if(y[i]!=0)
System.out.println("选取了第"+"i个物品");
}//end for
}//end test
}//end class
4 动态规划算法
由于本题中的所有物品的体积均为整数，经过几次的选择后背包的剩余空间可能会相等，在搜索中会重复计算这些结点，符合动态规划中子问题重叠的性质，即相同的n和c时，f(n,c)会重复计算。所以，如果我们把搜索过程中计算过的结点的值记录下来，以保证不重复计算的话，速度就会提高很多。这是简单的“以空间换时间”。
可以修改上述递归算法中的f(n,c)函数，通过用memo数组记录中间结果的f(n,c)值（这里用备忘录的自顶向下的方式实现动态规划算法）
//n为第n个待选物品,用memo记录对应的f(n,c)的中间结果
int[][] memo=new int[n][c+1];
//初始化
for(int i=0;i<n;i++){
for(int j=0;j<c+1;j++)
memo[i][j]=-1;
}//end for
private int f(int n,int c){
//memo
if(memo[n][c]!=-1)
return memo[n][c];
//base case
if(n==0 || c=0) //当物品数量为0，最优解为0
return 0;
else{
for(int i=n-1;i>=0;i++){ //从最终目标出发，自顶向下求解。从当前所剩物品的最后一个物品开始向前，逐个判断是否要添加到背包中
//如果当前要判断的物品重量大于背包当前所剩的容量，那么就不选择这个物品，在这种情况的最优解为f(n-1,C)
if(w[i]>c){
y[i]=0;
memo[n][c]=f(n-1,c);
return memo[n][c];
}//end if
else{
//如果当前待判断的物品重量wi<C,那么就选取f(n-1,C)和vi+f(n-1,C-wi)中的最大值
int temp1=f(n-1,c); //不放入第n个物品
int temp2=f(n-1,c-w[i])+v[i]; //放入第n个物品
//返回选择物品i和不选择物品i中最优解大的一个
if(temp1>temp2){
y[i]=0; //这种情况下表示物品i未被选取
memo[n][c]=temp1;
return temp1;
}//end if
else{
y[i]=1; //物品i被选取
memo[n][c]=temp2;
return temp2;
}//end else
}//end else
}//end for
}//end else
}//end f
【算法二】自底向上求解
//物品对象抽象
public class Thing{
public int weight; //物品重量
public int value; //物品价值
}//end class Thing
//物品thing，重量c
//thing物品数组,totalWeight总重量
public int f(Thing[] thing,int totalWeight){
//输入控制
if(thing==null || totalWeight<=0)
return 0;
int number=thing.length;
if(number==0)
return 0;
else if(number==1){ //只有一件物品时，直接返回
return thing[0].value;
} //end if
//数组用于存储中间结果，其中的对象Thing的属性value当前的总价值,weight记录当前的剩余重量
Thing[] valueArr=new int[number];
int maxValue=0; //记录最大价值，用于构造最优解
//初始化
valueArr[0].weight=totalWeight;
valueArr[0].value=0;
maxValue=valueArr[0].value;
//自定向上构造最优解
for(int i=1;i<number;i++){
if(valueArr[i-1].weight==0) //当剩余重量为0或者物品选完时，结束算法
return maxValue;
if(thing[i].weight> valueArr[i-1].weight){
valueArr[i].weight=valueArr[i-1].weight;
valueArr[i].value=valueArr[i-1].value;
}//end if
else {
value=valueArr[i-1].value+ thing[i].value; //选择物品i,v[n]+f(n-1, C-w[n])
weight=valueArr[i-1].weight-thing[i].weight;
//比较
if(valueArr[i-1].value > value){ //第i件不放进去，这时所得价值为:f(n-1,c)
valueArr[i].weight=valueArr[i-1].weight;
valueArr[i].value=valueArr[i-1].value;
}//end if
else{ //第i件放进去，这时所得价值为：v[n]+f(n-1, c-w[n])
valueArr[i].weight=weight;
valueArr[i].value=value;
}//end else
//存储最优解
maxValue=Math.max(maxValue,valueArr[i].value);
}//end else
}//end for
//返回最优解
return valueArr[i].value;
}//end f