标签：背包 int tw 装满 rw static 回溯 new op
public static void main(String[] args) {
int op[] = new int [n+1];
int x[] = new int [5];
int rw = 0;
for(int i = 1;i<=n;i++)
rw+=w[i];//剩余物品重量，初始值为所有物品重量之和
dfss(1,0,rw,0,op);
printtt();
}
public static int w[] = {0,5,3,2,1};
public static int v[] = {0,4,4,3,1};
public static int n = 4;
public static int weigh = 6;
public static int maxV = 0;
public static int[]x = new int[n+1];//记录一下
public static void dfss(int i,int tw,int rw,int tv,int op[]) {
// tw 现在已经装了多少东西了 rw还剩多少物品等待被装
if(i>n) {//找到了叶子节点,
if(tw==weigh&&maxV<tv) {//正好装完且现在的价值大于目前的价值
maxV = tv;
for(int j = 1;j<=n;j++) {
x[j] = op[j];//记录
}
}
}
else {
if(tw+w[i]<=weigh) {//左剪枝
//System.out.println("最大");
op[i] = 1;
dfss(i+1,tw+w[i],rw-w[i],tv+v[i],op);
}
if(tw+rw-w[i]>=weigh) {//右剪枝
// System.out.println("最大");
op[i] = 0;
dfss(i+1,tw,rw-w[i],tv,op);
}
}
}
public static void printtt() {
for(int i = 1;i<=n;i++) {
if(x[i]==1){//选了这个包了
System.out.print("背包序号为"+i+" ");
System.out.print("背包重量为"+w[i]+" ");
System.out.println("背包价值为"+v[i]+" ");
}
}
System.out.println("最大价值为"+maxV);
}
标签：背包,
int,
tw,
装满,
rw,
static,
回溯,
new,
op
From： https://blog.csdn.net/qq_62691586/article/details/144534224