동적 계획(2)가방 문제 응용

제목.
작은 Q 는 관문 을 돌파 하 는 게임 을 하고 있 습 니 다.관문 에서 n n n 마리 의 몬스터 를 차례로 만 날 수 있 습 니 다.모든 몬스터 는 자신의 무력 치 를 가지 고 있 습 니 다.순 조로 운 관문 을 통과 하기 위해 서 는 몬스터 에 게 금화 로 뇌물 을 주 고 뇌물 을 받 은 몬스터 를 데 리 고 계속 관문 을 통과 해 야 한다.모든 몬스터 의 총 무력 치가 만난 몬스터 의 무력 치보다 낮 으 면 계속 뇌물 을 줘 야 한다.실례 지만,작은 Q 는 적어도 몇 개의 금 화 를 사용 해 야 관문 을 성공 적 으로 통과 할 수 있 습 니까?
입 출력
몬스터 의 수량 n n n,몬스터 한 마리 의 무력 치,뇌물 에 필요 한 금화 수량.

//     
int n = 5;
int[] power = {4,1,1,1,5}; //      
int[] cost = {1,2,2,2,3}; //        
//     3   ，         

분석 하 다.
가방 문제 에 대한 전형 적 인 응용 을 비교 하고 분자 문 제 를 어떻게 그 리 느 냐 가 이 문 제 를 해결 하 는 관건 이다.
이 문 제 를 보기 전에 가방 문 제 를 보 는 것 을 추천 합 니 다.만약 에 낯 설 면 이 글 이 도움 이 될 것 이 라 고 믿 습 니 다.BAT 면접 의 동태 계획(1)가방 문 제 를 상세 하 게 풀 수 있 습 니 다.
무력 치가 자신 을 초과 하 는 몬스터 에 대해 우 리 는 매수 하 는 것 을 선택해 야 한다.무력 치가 자신 보다 낮은 몬스터 에 대해 우 리 는 그 후의 상황 을 따 져 봐 야 한다.이 몬스터 를 매수 하 는 것 은 우리 에 게 아무런 의미 가 없 을 수도 있 고,우리 가 최소한 의 비용 으로 뒤의 관문 을 통과 하 는 데 도움 이 될 수도 있다.
가방 문제 의 가방 용량 이 제한 되 어 있 는 것 처럼 우 리 는 제 한 된 가방 공간 에서 가능 한 한 불 러 온 물품 의 가 치 를 최대 로 하고 싶 습 니 다.이 문제 에서 우리 금화 의 수량 도 제한 되 어 있 습 니 다.최대 치 는 모든 몬스터 가 동시에 소비 하 는 금화 m a x 를 매수 하 는 것 입 니 다.c o i n s max\_coins max_coins,우 리 는 가능 한 한 적은 금 화 를 사용 하여 문 제 를 해결 하고 싶 습 니 다.
고찰 전 i-1 i-1 i-1 마리 몬스터 가 문 제 를 해결 할 수 있 는 지 없 는 지 를 고찰 할 때 우리 의 기준 은 몬스터 를 지 닌 총 무력 치가 i i 마리 몬스터 보다 클 수 있 는 지 하 는 것 이다.만약 가능 하 다 면,우 리 는 제 i i i 몬스터 를 매수 할 필요 가 없다.반대로,우 리 는 그것 을 매수 해 야 한다.지 니 고 있 는 총 무력 치 에 도 변화 가 생 길 것 이다.그래서 가방 문 제 를 비교 해 보면 실제로 저장 해 야 할 중간 결 과 는 몬스터 를 휴대 하 는 총 무력 치 라 는 것 을 알 수 있다.
상태 전환 방정식 은 P[i][j]=m a x(P[i-1][j],P[i-1][j-c o s t[i]]+p o w e r[i])P[i]=max(P[i-1][j],P[i-1][j-cost[i]]]+power[i]]P[j]=max(P[i-1],P[i-1]]][j-cost[i]]]]]+power[i]]]
P[i][j]P[i][j]P[i][j]j j 개의 금 화 를 사용 하여 전 i-1 i-1 i-1 몬스터 의 관문 을 통과 한 후 지 니 고 있 는 무력 치.
왜 최대 무력 치 입 니까?
이것 은 숨겨 진 최적화 목표 로 무력 치가 클 수록 정세 가 우리 에 게 유리 한 방향 으로 기울 고 다음 문 제 를 해결 할 가능성 이 높다 는 것 으로 이해 할 수 있다.
상태 방정식 은 어떻게 생 겼 습 니까?
만약 j j 개의 금 화 를 사용 하여 전 i-1 i-1 i-1 몬스터 의 관문 을 통과 한 후 지 니 고 있 는 무력 치가 i i 마리 몬스터 보다 크다 면 우 리 는 P[i][j]=P[i-1][j]P[i][j]=P[i-1][j]=P[i-1][j]P[i]=P[i]=P[i-1][j]를 사용 할 수 있다.
하지만 지금 j j 의 금화 가 있 는 이상 우리 가 그 중의 c o s t[i]cost[i]cost[i]cost[i]매 를 꺼 내 서 제 i i 의 몬스터 를 매수 하면 최종 무력 치가 더 좋 지 않 을 까?우 리 는 j-c o s t[i]j-cost[i]j-cost[i]개의 금화 가 전 i-1 i-1 관문 을 통과 한 후의 무력 치 와 제 i i i 몬스터 의 무력 치 를 더 해 얻 은 값 을 고찰 해 야 한다.즉 P[i-1][j-c o s t[i]+p o w e r[i]P[i-1][j-cost[i]]]+power[i-1][j]P[i-1][j]P[i-1][j]P[i-1][j]P[i-1]
최적화 와 실현
실현 할 때 우 리 는 하위 문 제 를 해결 할 수 없 는 상황 에 직면 하 게 된다.왜냐하면 P[i][j]P[i][j]P[i][j][i]는 j j 금 화 를 사용 하여 전 i i i 몬스터 의 관문 을 통과 한 후에 지 니 고 있 는 무력 치 를 나타 내 는 것 이다.j j 의 수 치 는 0～m a x 이다.c o i n s max\_coins max_coins 사이,그래서 j j j 는 i i i 몬스터 를 뚫 기 에 충분 하지 않다.예 를 들 어 j=0 j=0 j=0 j=0 일 때.
우 리 는-1 을 사용 하여 하위 문제 가 해결 되 지 않 음 을 표시 할 수 있 습 니 다.그러면 최종 결 과 는 마지막 줄 앞에서 첫 번 째 는-1 이 아 닌 값 을 검색 하고 해당 하 는 j j j j 로 돌아 가 는 것 입 니 다.이것 이 바로 전 i i 관문 을 통과 한 가장 작은 j j j j j 수치 입 니 다.
최적화 후 1 차원 배열 로 문 제 를 해결 하고 상태 전환 방정식 은 P[j]=m a x(P[j],P[j-c o s t[i]+p o w e r[i]P[j]=max(P[j],P[j-cost[i]]]]+power[i]P[j]=max(P[j],P[j-cost[i]]]]]+power[i])
어떻게 최적화 하 느 냐 에 따라 제 가 위 에서 추천 한 글 도 서술 이 있 습 니 다.여기 서 간단하게 말 하면 상태의 업 데 이 트 는 이전 줄 에 만 의존 하고 매번 아래 표 시 를 잘못 하면 우 리 는 1 차원 배열 을 사용 하여 뒤에서 업 데 이 트 를 하면 2 차원 배열 과 같은 효 과 를 실현 할 수 있 습 니 다.
1 차원 배열 을 사용 하여 공간 에서 의 비용 은 2 차원 배열 의 1 n\frac{1}{n}n1 입 니 다.이러한 최적화 는 우리 가 반드시 파악 해 야 할 것 입 니 다.특히 면접 필기시험 에서.최적화 도 어렵 지 않 습 니 다.줄 표시 i i 의 부분 을 제거 할 뿐 다른 부분 은 다 르 지 않 습 니 다.
다음은 실 현 된 자바 코드 입 니 다.

	/*
	 *   int        
	 */
    private static int MinCoins(int n, int[] power, int[] cost) {
        if (power.length == 0) return 0;
        int max = 0;
        for (int c : cost) max += c;  //     max   

        int[] P = new int[max + 1];
        for (int p : P) p = -1;  //    -1
        for (int i = 0; i < n; i++) {
            for (int j = max; j >= 0; j--) { //       
                int temp1 = P[j] >= power[i] ? P[j] : -1; //            
                int temp2 = (j >= cost[i]) && (P[j - cost[i]]!= -1) ? //          
                        P[j - cost[i]] + power[i] : -1;

                P[j] = temp1 > temp2 ? temp1 : temp2;
            }
        }
        //   
        int index = 0;
        for (; index < max+1;index++) {
            if(P[index] != -1) break;
        }
        return index;
    }

레 퍼 런 스
블 로그 원:텐 센트 2019 실습 필기시험
본문 이 끝 났 습 니 다.메 시 지 를 환영 합 니 다.