동적 계획 - 채굴

4581 단어 알고리즘
한 나라 에서 5 개의 금광 을 발 견 했 는데 금광 마다 금 매장량 이 다 르 고 발굴 에 참여 해 야 하 는 노동자 수도 다르다.채굴 에 참여 한 노동자 의 총 수 는 10 명 이다.모든 금광 은 다 파 든 지 안 파 든 지 반 사람 을 보 내 금광 의 반 을 파 낼 수 없다.가능 한 한 많은 금 을 얻 으 려 면 어떤 금광 을 캐 야 하 는 지 절차 적 으로 풀 어야 한다.
첫 번 째 400 금 / 5 명, 두 번 째 500 금 / 5 명, 세 번 째 200 금 / 3 명, 네 번 째 300 / 4 명, 다섯 번 째 350 / 3 명.
코드 는 다음 과 같 습 니 다:
/**
 * Created by Owen Chan
 * On 2018-01-27.
 */

public class GoldDig {
    public static void main(String[] argv) {
        System.out.println("Most gold");
        int worker = 10;
        int[] gold = new int[]{400, 500, 200, 300, 350};
        int[] person = new int[]{5, 5, 3, 4, 3};

        getMostGold(worker, gold, person);
        System.out.println("Most gold: " + getMostGold(worker, gold, person));
    }

    private static int getMostGold(int worker, int[] gold, int[] person) {

        int[] preArray = new int[worker];
        int[] tempArray = new int[worker];

        for (int i = 0; i < worker; i++) {
            preArray[i] = person[0] <= i + 1 ? gold[0] : 0;
            System.out.println(preArray[i]);
        }

        for (int goldIndex = 1; goldIndex < gold.length; goldIndex++) {
            for (int workerIndex = 0; workerIndex < worker; workerIndex++) {
                int lastWorker = workerIndex + 1 - person[goldIndex]; //     
                if (lastWorker > 0) {  //       
                    tempArray[workerIndex] = Math.max(preArray[lastWorker - 1] + gold[goldIndex], preArray[workerIndex]);
                } else if (lastWorker == 0) { //        
                    tempArray[workerIndex] = Math.max(gold[goldIndex], preArray[workerIndex]);
                } else {  //        
                    tempArray[workerIndex] = preArray[workerIndex];
                }
            }
            System.arraycopy(tempArray, 0, preArray, 0, tempArray.length);
            for (int i = 0; i < preArray.length; i++) {
                System.out.println(preArray[i]);
            }
        }
        return preArray[worker - 1];
    }
}

좋은 웹페이지 즐겨찾기