0/1背包暴力解法,giegie不温柔了
0/1背包问题
有 n 件物品,第 i 件的重量和价值分别是 wi 和 vi 。要将这 n 件物品的一部分装入容量为c 的背包中,要求每件物品或整个装入或不装入。0/1背包问题就是要给出装包算法,使得装入背包的物品的总价值最大。本节采用回溯方法求解,选择出满足目标函数极大化和重量要求的一个子集。
0/1一般使用动态规划来写的,这里介绍的是暴力的回溯方法。
思路解析
解空间树:回溯方法的第一步就是确定解空间树,对于一个物品有要和不要两种选择。所以这是一颗二叉树。我们要得到的是一个解向量X={1,0,1,0,0…},表示选取那些节点。
怎么做呢?
1.对于效益数组V和重量数组W,根据wi/vi(性价比)来排序。我们先把性价比高的放进去。
2.可是保证先放性价比最高的就能实现是最优结果吗?看看下面这里例子
因此,对性价比优先的方法做出改进。
即,加入判断:
如果在不选本物品,而把后面的物品尽可能的装入的情况下,价值比最大收益大,就继续递归
如果
import java.util.Arrays;
public class Bag0_1 {
public static void main(String[] args) {
int[] val ={60,100,120};
int[] vol ={10,20,30};
bag b=new bag(50,val,vol);
b.sort();
b.getIn(0,0,50);
System.out.println(b.fv+" "+Arrays.toString(b.BC));
}
}
class bag{
/***
* 属性: 1.容量C 2.价值数组val 3.体积数组vol 4.解向量X 5.最大效益fc 6.解向量长度n
* 方法: 1.构造方法 2.性价比排序 3.回溯
* getIn(t,cv,r)
* t:当前步骤
* cv:当前价值
* cw:剩余容量
*/
public int C,fv=-1,n;
public int[] Val,Vol;
public int[] X,BC;
public bag(int c, int[] val, int[] vol) {
C = c;
Val = val;
Vol = vol;
X=new int[Val.length];
n=X.length;
}
public int[] sort(){
int[] X=new int[Val.length];
for (int i=0;i<=Val.length-1;i++){
X[i]=Val[i]/Vol[i];
}
// 对X做一个冒泡排序
for (int i=X.length-1;i>=0;i--){
for (int j=0;j<i;j++){
if (X[j]<X[j+1]){
X=swap(X,j,j+1);
Vol=swap(Vol,j,j+1);
Val=swap(Val,j,j+1);
}
}
}
return X;
}
public int[] swap(int[] X,int a,int b){
int t;
t=X[b];
X[b]=X[a];
X[a]=t;
return X;
}
public void getIn(int t,int cv,int cw){
if (t>=n&&cv>fv){
fv=cv;
BC=X;
}
else if (t<n){
if (Vol[t]<=cw){
X[t]=1;
getIn(t+1,cv+Val[t],cw-Vol[t]);
}
if (cv+Rest(t+1,cw)>fv){
X[t]=0;
getIn(t+1,cv,cw);
}
}
}
public double Rest(int t,int rc){
double rv=0;
for (;t<n&&Vol[t]<=rc;t++){
rv+=Val[t];
rc-=Vol[t];
}
return rv;
}
}
版权声明:本文为Dthsdlmaq原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。