动态规划(2)01背包问题

时间:2022-01-19 15:04:41

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个属性:当前价值和,当前剩余的重量)。

画决策树时先构造一边直到叶子节点,然后再回溯

动态规划(2)01背包问题

动态规划(2)01背包问题

动态规划(2)01背包问题

从决策树的叶子节点可以看出,最大价值为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