搜狐2018筆試題二

昨晚沒寫完，今天還是補上來，不知道正确率是多少了，自己運作是可以的。

有什麼錯誤歡迎大家留言相告，互相學習。

對于1*1、2*2、3*3、4*4、5*5、6*6大小的産品，裝在6*6的包裹裡，求得最少包裹數。

輸入：

0 0 4 0 0 1

7 5 1 0 0 0

0 0 0 0 0 0

輸出：

2

1

裝包裹的問題最優化解題思路：

最考慮體積最大的産品，再整體考慮剩餘空間裝小體積産品~

import java.util.ArrayList;
import java.util.Scanner;

public class Sohub {

    /**
     * @param args
     */
    /*解題思路：
     * 先裝所有大體積産品：6*6、5*5、4*4、3*3
     * 此時包裹至少a[5]+a[4]+a[3]+(a[2]+3)/4個
     * 裝3*3産品的包裹未裝滿的情況：
     * 隻有一個3*3時，還可裝2*2的産品5個，同理，數組設為u[]=[0,5,3,1];
     * 餘下隻考慮剩餘空間與2*2、1*1的關系即完成。
     * */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int count = ;
        int a[] = new int[];
        ArrayList<Integer> results= new ArrayList<Integer>();
        while(true){
            for(int i=;i<;i++){
                a[i] = in.nextInt();
                if(a[i] == )count++;
            }
            if(count == )break;
            int x=SolveProblem(a);
            results.add(x);
            count = ;
        }
        for(int i=;i<results.size();i++){
            System.out.println(results.get(i));
        }
    }

    public static int SolveProblem(int a[]){
        int t[]={,,,};//這是3*3的箱子剩餘自己裝的時候
        int total=,x,y,n;
        total = a[]+a[]+a[]+(a[]+)/;
        x = t[a[]%]+*a[];//剩餘空間可裝2*2的個數

        //剩餘空間不夠裝2*2時，需要另加包裹
        if(a[] > x){
            total += (a[]-x+)/; 
        }
        //此時包裹剩餘空間
        n=*total-*a[]-*a[]-*a[]-*a[]-*a[];

        if(a[]>n){
            total+=(a[]-n+)/;
        }
        /*for(int i=0;i<a.length;i++){
            System.out.println(a[i]);
        }*/
        return total;
    }

}