貪心法解決0-1背包問題

貪心法是指 在背包沒有裝滿之前,隻要能裝得下就裝進背包.

在使用貪心法解決0-1背包問題主要在于分解方案和貪心選擇方案.(貪心法不能保證最優解)

為了盡可能的得到最優解,選擇物品時,總是選擇v[i]/w[i]最大的物品裝進去

是以在程式的開始,應首先對物品按照v[i]/w[i]從大到小進行排序,是以在排序的過程中可以定義一個數組來記錄原本的第i個物品在排序之後放在第幾位,即th[i]=k:原來的第i個物品放在現在的第K個裡面.(也可以定義一個結構體在結構體中記錄原來的次序)

public class tanXin {
	int TanXin(int[] w,int[] v,int[] x,int[] th,int max,int Total){
	    int k = 0,q,c=Total;
	    int sum =0;
	    while(k<max){
	        if(w[th[k]]< c){
	            sum+=v[th[k]];
	            c-=w[th[k]];
	            x[th[k]]=1;
	       }
	       k++;
	    }
		return sum;
	}
}