inputpack.java

此小程序用java实现了可以分割的背包问题

package divpack;
import java.util.*;
public class Inputpack {
public final float M=20;
Structure [] instance;
double [] x;
int n;
public Inputpack(int n){
	this.n=n;
	instance=new Structure[n];
	x=new double[n];
	//int i;
	float m,t;
		for(int i=0;i<n;i++){
			int j=i+1;
		System.out.println("请分别输入第" + j+"物体的重量和价值");
		Scanner scanner=new Scanner(System.in);
		m=Float.parseFloat(scanner.next());
		t=Float.parseFloat(scanner.next());		
		instance[i]=new Structure(t,m);
		x[i]=0.0;
	    }
	//new MergeSortAlgorithm().MergeSort(instance, 0, instance.length);
		for(int i=0;i<n;i++){
			System.out.print(instance[i].p+"");
			System.out.print(instance[i].w+"");
			System.out.println(instance[i].v);
		}
		MyComparator mycom=new MyComparator();
		Arrays.sort(instance, mycom);
}
float knapsack_greedy(){
	float m=M,p=0;
	//m=M;
	for(int i=0;i<n;i++){
		if (instance[i].w<=m){
			x[i]=1;
			m=m-instance[i].w;
			p=p+instance[i].p;
			System.out.println("第"+ i +"件物品，价值为"+p);
		}else{
			x[i]=m/instance[i].w;
			p+=x[i]*instance[i].p;
			System.out.println("最后选择"+ i +"件商品的一部分");
			break;
		}
	}
	return p;
}
public static void main(String[] args){
	Inputpack a=new Inputpack(10);
	System.out.println(a.knapsack_greedy());
}
}