题目描述
有n个物品，第i个物品重量为wi，价值为vi，现有一背包容量为C，要求把物品装入背包得到最大价值，并且要求出这些选取的物品。 要求用回溯法求解。
输入
多组测试数据，请处理到文件尾，一个整数表示物品的数量n，后一行有n个整数，代表价值，再后一行有n个整数，代表重量，最后有一个整数C代表背包容量,1<=n<=15,1<=vi<=30,1<=wi<=30,1<=C<=80。
输出
背包的最大总价值和所选取的物品，如果选取的方案有多种，请输出字典序最小的那种方案，每组测试数据应输出一行，在这里字典序最小的意思是，我们假设存在两种不同方案S,T所能得到的总价值相同且是最大的，对于方案S种选取|S|种物品，方案T选取|T|种物品，对于i=1,2…j-1，我们有si = ti，但sj < tj,则方案的S的字典序比方案T的字典序要小。由于没有使用special judge，所以如果选取得方案是S，请按照从小到大的顺序输出方案S中的物品下标。
样例输入 Copy
5
6 3 6 5 4
2 2 4 6 5
8
样例输出 Copy
15 1 2 3
package book;
import java.util.Scanner;
public class backtrace01 {
static int n;//物品数量
static int v[];//价值
static int w[];//重量
static int cc,bc;//当前背包重量和当前最佳背重量
static int Maxc,Cmax;//背包最大容量，背包剩余容量
static int Cway[],Fway[];//当前装物品的方案，最佳装物品的方案
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();//物品数量
v=new int[n];
w=new int[n];
Cway=new int[n];
Fway=new int[n];
cc=bc=0;
for(int i=0;i<n;i++) {
v[i]=sc.nextInt();
}
for(int i=0;i<n;i++) {
w[i]=sc.nextInt();
}
Maxc=sc.nextInt();//最大背包容量
Cmax=Maxc;
backtrace(0);
print();
}
private static void print() {
System.out.print(bc+" ");
for(int i=0;i<n;i++) {
if(Fway[i]==1) {
System.out.print(i+1+" ");
}
}
}
private static void backtrace(int i) {
if(i>n-1) {
if(cc>bc) {
bc=cc;
for(int k=0;k<n;k++) {
Fway[k]=Cway[k];
}
}
}else {
if(Cmax>=w[i]) {
Cmax-=w[i];
cc+=v[i];
Cway[i]=1;
backtrace(i+1);
Cmax+=w[i];
cc-=v[i];
Cway[i]=0;
}
if(check(i+1)+cc>bc) {
backtrace(i+1);
}
}
}
private static int check(int i) {
int count=0;
for(int j=i;j<n;j++) {
count+=v[i];
}
return count;
}
}第二篇过程详解
package lianxi5;
import java.util.Scanner;
public class Main56{
static int num, maxc,cmax,currentbest,best;
static int v[],w[],
currentway[],Fway[];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
num=sc.nextInt();//物品数量
v=new int[num+1];//价值背包
w=new int[num+1];//重量背包
currentway=new int[num+1];//当前背包
Fway=new int[num+1];//最好背包
for(int i=1;i<=num;i++) {
v[i]=sc.nextInt();//依次放价值
}
for(int i=1;i<=num;i++) {
w[i]=sc.nextInt();//依次放价值
}
maxc=sc.nextInt();//最大背包容量
cmax=maxc;//背包容量赋值
currentbest=0;//当前最佳
best=0;//最终最佳
backtrack(1);
print();
}
}
private static void print() {
System.out.print(best+" ");
for (int i=1;i<=num ;i++) {
if(Fway[i]==1)
System.out.print(i+" ");
}
}
private static void backtrack(int i) {
if(i>num){//如果放到最後一個物品，那一定是最佳方案
if(currentbest>best){//判斷當前的最佳最佳和之前的最佳方案
best=currentbest;//交換
for (int j = 1; j <=num; j++) {
Fway[j]=currentway[j];//交換
}
}
}
else {//第一种选
if(maxc>=w[i]){//当前剩余容量
maxc-=w[i];//更新剩余容量
currentbest+=v[i];//更新当前最佳容量
currentway[i]=1;//将选中的物品标志更改为
backtrack(i+1);//继续回溯
maxc+=w[i];
currentbest-=v[i];
currentway[i]=0;
}//第二种不选
if(check(i+1)+currentbest>best)
backtrack(i+1);//当前物品大于剩余容量，但是除了他不放，把之后的物品都放入还可以得到一个优于现有解
//当前物品不选继续递归下一个
}
}
private static int check(int k) {
int bound=0;
for(int j=k;j<=num;j++)
bound+=v[j];
return bound;
}
}