想在最后加一句输出最优解的语句,但是提示出错,求最优解的就是 Traceback函数package com.sohu;import javax.swing.JOptionPane;
public class Knapsack {
//int[][]m=new int[50][];
public static int[][] Knapsacker(int[]v,int[]w,int c,int n){
int[][]m=new int[n][c+1];
n--;
int jMax=Math.min(w[n], c);
int j=0;
for(j=0;j<jMax;j++)
m[n][j]=0;
for(j=w[n];j<=c;j++)
m[n][j]=v[n];
for(int i=n-1;i>=0;i--){
int jmax=Math.min(w[n], c);
for(j=0;j<jmax;j++)
m[i][j]=m[i+1][j];
for(j=w[i];j<=c;j++)
m[i][j]=Math.max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
return m;
}
public static int[] Traceback(int[]w,int c,int n,int[][]m){
int[]x=new int[50];
for(int i=0;i<n;i++)
if(m[i][c]==m[i+1][c]) x[i]=0;
else{
x[i]=1;
c-=w[i];
}
return x;
}
public static void main(String[] args) {
int c=10;
int n=5;
int[][]k=new int[n][c+1]; int w[]={2,2,6,5,4};
int v[]={6,3,5,4,6};
k=Knapsacker(v,w,c,n);
String output1="";
for(int i=n-1;i>=0;i--){
for(int j=0;j<=c;j++)
output1+=k[i][j];
output1+="\n";
}
JOptionPane.showMessageDialog(null,output1+"\n"+"0-1背包的最优值为 "+k[0][10],"output1",JOptionPane.INFORMATION_MESSAGE); }
}
结果:
00006666666
0000066661010
0000006661010
0033336691010
006699991212150-1背包的最优值为 15
public class Knapsack {
//int[][]m=new int[50][];
public static int[][] Knapsacker(int[]v,int[]w,int c,int n){
int[][]m=new int[n][c+1];
n--;
int jMax=Math.min(w[n], c);
int j=0;
for(j=0;j<jMax;j++)
m[n][j]=0;
for(j=w[n];j<=c;j++)
m[n][j]=v[n];
for(int i=n-1;i>=0;i--){
int jmax=Math.min(w[n], c);
for(j=0;j<jmax;j++)
m[i][j]=m[i+1][j];
for(j=w[i];j<=c;j++)
m[i][j]=Math.max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
return m;
}
public static int[] Traceback(int[]w,int c,int n,int[][]m){
int[]x=new int[50];
for(int i=0;i<n;i++)
if(m[i][c]==m[i+1][c]) x[i]=0;
else{
x[i]=1;
c-=w[i];
}
return x;
}
public static void main(String[] args) {
int c=10;
int n=5;
int[][]k=new int[n][c+1]; int w[]={2,2,6,5,4};
int v[]={6,3,5,4,6};
k=Knapsacker(v,w,c,n);
String output1="";
for(int i=n-1;i>=0;i--){
for(int j=0;j<=c;j++)
output1+=k[i][j];
output1+="\n";
}
JOptionPane.showMessageDialog(null,output1+"\n"+"0-1背包的最优值为 "+k[0][10],"output1",JOptionPane.INFORMATION_MESSAGE); }
}
结果:
00006666666
0000066661010
0000006661010
0033336691010
006699991212150-1背包的最优值为 15
解决方案 »
免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货