第1楼 2007-06-11 01:50 热学男儿 写道:

请高手帮忙，用分支限界法作一个0/1背包的程序

用分支限界法写一个0/1背包的程序，要用java语言写的，那位高手会，恳请帮忙啊，小弟跪求。

第2楼 2013-08-31 12:44 Robot :

请高手帮忙，用分支限界法作一个0/1背包的程序 相关

第3楼 2007-06-11 19:29 秋水长天 写道:

public class knapsack {

public knapsack(int c, int [] s, int [] v) {
this.c = c + 1 ;
this.s = s ;
this.v = v ;
this.track = new int [s.length] ;
}
public int doKnapsack(){
this.n = s.length + 1 ;
value = new int [n][c] ;
for (int i = 0 ; i < this.n ; i ++ ){
value[i][0] = 0 ;
}
for (int i = 0 ; i < this.c ; i ++ ){
value[0][i] = 0 ;
}
for (int i = 1 ; i < this.n ; i ++)
for (int j = 1 ; j < this.c ; j ++){
value[i][j] = value[i-1][j] ;
if (s[i-1] <= j) {
value[i][j] = max(value[i][j] , value[i-1][j-s[i-1]]+v[i-1]) ;
}
}
return value[n-1][c-1] ;
}

public void printTrack(){//打印0/1背包最优解时选择的背包号码
int temp = c-1 ;
for (int i = n-1 ; i > 0 ; i --){
if (value[i][temp] == value[i-1][temp]) track[i-1] = 0 ;
else {
track[i-1] = 1;
temp -= s[i-1] ;
}
}
System.out.println() ;
System.out.println("最优解情况下选取的背包是如下几个：") ;
for(int i=0 ; i< v.length ; i ++)
if (track[i] == 1) System.out.print(i+" ") ;
System.out.println() ;

}

private int max(int a, int b) {
return a>b?a:b ;
}

private int [] s ; // 每个物体所占容量
private int [] v ; // 每个物体的价值
private int c ; // 包容量
private int n ; // 总共物体个数
private int [][] value ; // 存储中间价值结果， value[n][c] 是结果， value[i][j] 表示i个物品 ， 最大j容量
private int [] track ; //track[i]=0 1 , 表示第i个物品是否被选
}

package homework.algorithm;

import java.util.*;
public class TestKnapsack {


/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
//需要生成包的容量c， 生成包的重量数组s和价值数组v
Random rand = new Random() ;
int c = rand.nextInt(50)+1 ;
int n = rand.nextInt(20)+1 ;
int [] s = new int [n] ;
int [] v = new int [n] ;
System.out.println("背包容量为"+c) ;
for (int i = 0 ; i < n ; i ++){
s[i] = rand.nextInt(10)+1 ;
v[i] = rand.nextInt(30)+1 ;
}
System.out.println("总共有物品"+n+"件") ;
System.out.println("每件物品重量为") ;
for (int i : s) System.out.print(i+" ") ;
System.out.println() ;
System.out.println("每件物品对应价值为") ;
for (int i : v) System.out.print(i +" ") ;
System.out.println() ;
knapsack ks = new knapsack(c,s,v) ;
int rt = ks.doKnapsack() ;
System.out.println(rt) ;
System.out.println(test(0,c,s,v)) ;
ks.printTrack() ;
}

public static int test(int i , int c, int [] s, int[] v){
if (i==s.length-1) return (c<s[i])?0:v[i] ;
if (c < s[i]) return test(i+1,c,s,v) ;
int a = test(i+1,c,s,v) ;
int b = test(i+1,c-s[i],s,v)+v[i] ; //shit! 开始写成c-v[i] 了！
return (a>b)?a:b;
}

}