【趣学算法】Day2 贪心算法——最优装载问题

int solve1(int n,double W){
	double tmp=0.0;//tmp为已装载到船上的古董重量
    int ans=0; //ans为已装载的古董个数，初始化为0
    for(int i=0;i<n;i++){
        tmp+=w[i];
        if(tmp<=W)
            ans++;
        else
            break;
    }
    return ans;
} 

int solve2(int n,double w){//优化算法 
	double tmp=0.0;//tmp为已装载到船上的古董重量
	int ans=n; //ans为已装载的古董个数，初始化为n
    for(int i=0;i<n;i++){
        tmp+=w[i];
        if(tmp>=w){//最后一次才满足条件 
        	if(tmp==w)
        		ans=i+1;
        	else
        		ans=i;
        	break;
		}     
    }
    return ans;
}

public class algorithm02 {
    public static void main(String[] args) {
        int[] w = {4, 10, 7, 11, 3, 5, 14, 2};
        int W = 30; // 船的载重量
        int temp;
        for (int i = 0; i < w.length-1; i++) {
            for (int j = 0; j < w.length - i - 1; j++) {
                if (w[j] > w[j + 1]) {
                    temp = w[j];
                    w[j] = w[j + 1];
                    w[j + 1] = temp;
                }
            }
        }
        System.out.println("古董重量排序后为：");
        for (int j = 0; j < w.length; j++) {
            System.out.print(w[j] + " ");
        }
            add02 a2 = new add02();
            int ans = a2.solve2(8 , W , w);
            System.out.println("\n总共装入了" + ans + "个古董");
    }
}

// add02类
public class add02 {
    public int solve2(int n , int W ,int w[]){//优化算法
        double tmp = 0.0;//tmp为已装载到船上的古董重量
        int ans = 0; //ans为已装载的古董个数，初始化为n
        for(int i = 0; i < n; i++){
            tmp += w[i];
            if(tmp >= W){//最后一次才满足条件
                if(tmp == W)
                    ans = i+1;
                else
                    ans = i;
                break;
            }
        }
        return ans;
    }
}