背包问题回溯法

01背包回溯法复杂度_回溯算法-0-1背包问题

(1)算法描述

给定num种物品和⼀背包。物品i的重量是weighti>0，其价值为pricei>0，背包的容量为capacity。问应如何选择装⼊背包中的物

品，使得装⼊背包中物品的总价值最⼤？

(2)举例

对于0-1背包问题的⼀个实例，num=4，capacity=7，price=[9,10,7,4]，weight=[3,5,2,1]。这4个物品的单位重量价值分

别为[3,2,3.5,4]，以物品单位重量价值的递减顺序装⼊物品。先装物品4，然后装⼊物品3和1。装⼊这3个物品后，剩余的背包容量

为1，只能装⼊0.2的物品2。由此可以得到⼀个解为x=[1,0.2,1,1]，其相应的价值为22。尽管这不是⼀个可⾏解，但可以证明其价

值是最优解的上届。因此，对于这个实例，最优解不超过22。

(3)算法描述

0-1背包问题是⼦集选取问题。0-1背包问题的解空间可⽤⼦集树表⽰。解0-1背包问题的与解最优装载问题⼗分相似，在搜索解空间树

时，只要其左⼦树结点是⼀个可⾏结点，搜索就进⼊其左⼦树。当右⼦树有可能包含最优解时才进⼊右⼦树搜索。否则将右⼦树剪枝。设

indeterminacyPrice是当前剩余物品价值总和；currentPrice是当前价值；bestPrice是当前最优价值。当currentPrice

+indeterminacyPrice<=bestPrice时，可剪去右⼦树。计算右⼦树中解的上界更好的⽅法是将剩余物品依其单位重量价值排序，然后依

次装⼊物品，直⾄装不下时，再装⼊该物品⼀部分⽽装满背包。由此得到的价值是右⼦树中的⼀个解。

(4)代码编写

publicclassKnapsack01{//背包容量

privatestaticIntegercapacity;//物品个数

privatestaticIntegernum;//物品重量数组

privatestaticInteger[]weight;//物品存放数组【0：不存放1：存放】

privatestaticInteger[]store;//物品最优装载数组序号【0：不存放1：存放】

privatestaticInteger[]bestIndex;//物品价值数组

privatestaticInteger[]price;//背包当前重量

privatestaticIntegercurrentWeight=0;//背包当前价值

privatestaticIntegercurrentPrice=0;//背包最优价值

privatestaticIntegerbestPrice=0;/***初始化数据*/

privatestaticvoidinitData(){undefined

Scannerinput=newScanner();

n("请输⼊背包容量:");

capacity=t();

n("请输⼊物品数量:");

num=t();

weight=newInteger[num];

store=newInteger[num];

bestIndex=newInteger[num];

n("请输⼊各个物品的重量:");for(inti=0;i<;i++){undefined

weight[i]=t();

store[i]=0;

bestIndex[i]=0;

}

price=newInteger[num];

n("请输⼊各个物品的价值:");for(inti=0;i<;i++){undefined

price[i]=t();

}

}/***根据物品价值降序排列，同时调整物品重量数组*/

privatestaticvoidsortDesc(){undefined

Integertemp;intchange=1;for(inti=0;i<&&change==1;i++){undefined

change=0;for(intj=0;j<-1-i;j++){if(price[j]

temp=price[j];price[j]=price[j+1];price[j+1]=temp;

temp=weight[j];weight[j]=weight[j+1];weight[j+1]=temp;

change=1;

}

}

}

}/***计算上届【判断】*/

privatestaticIntegerbound(inti){undefined

Integercleft=capacity-currentWeight;//记录剩余背包的容量

Integerp=currentPrice;//记录当前背包的价值//【已经按照物品价值降序排列，只要物品能装下，价值⼀定是最⼤】物品装⼊背包

时，⼀定要确保背包能装下该物品

while(i<&&weight[i]<=cleft){undefined

cleft-=weight[i];

p+=price[i];

i++;

}//将第i+1个物品切开，装满背包，计算最⼤价值

if(i

p=p+cleft*(price[i]/weight[i]);

}returnp;

}/***回溯寻找最优价值*/

privatestaticvoidbacktrack(inti){//递归结束条件

if(i==){if(currentPrice>bestPrice){for(intj=0;j<;j++){undefined

bestIndex[j]=store[j];

}

bestPrice=currentPrice;

}return;

}if(currentWeight+weight[i]<=capacity){//确保背包当前重量+物品i的重量<=当前背包容量，才有意义继续进⾏

store[i]=1;

currentWeight+=weight[i];

currentPrice+=price[i];

backtrack(i+1);

currentWeight-=weight[i];

currentPrice-=price[i];

}//剪枝函数【判断(背包当前价值+未确定物品的价值)⼤于背包最优价值，搜索右⼦树；否则剪枝】

if(bound(i+1)>bestPrice){undefined

store[i]=0;

backtrack(i+1);

}

}/***输出*/

privatestaticvoidprint(){undefined

n("n降序后各个物品重量如下:");

(weight).forEach(element->(element+""));

n();

n("降序后各个物品价值如下:");

(price).forEach(element->(element+""));

n();

n("物品最优装载数组序号【0：不装载1：装载】:");

(bestIndex).forEach(element->(element+""));

n();

n("背包最⼤价值：bestPrice="+bestPrice);

}publicstaticvoidmain(String[]args){//初始化数据

initData();//根据物品价值降序排列，同时调整物品重量数组

sortDesc();//回溯寻找最优价值

backtrack(0);//输出

print();

}

}

0-1背包核⼼代码

(5)输⼊输出

请输⼊背包容量:7请输⼊物品数量:4请输⼊各个物品的重量:3521请输⼊各个物品的价值:91074各个物品重量如下:5321各个物品

价值如下:10974物品最优装载数组序号【0：不装载1：装载】:0111背包最⼤价值：bestPrice=20

输⼊输出

(6)总结

0-1背包使⽤【回溯法-⼦集树】来求解，时间复杂度为O(2n)，使⽤深度优先遍历，递归⽅式求出最优解；

建议：可以依照我的代码，⾃⾏在纸上画⼀画，⾛⼀遍算法代码的详细流程，进⽽熟悉回溯法的核⼼思想，理解0-1背包问题的求解过

程。