동적 기획 - 완전 가방 시리즈

완전 가방 과 01 가방 의 차 이 는 01 가방 중 모든 아 이 템 을 선택 하거나 선택 하지 않 거나, 완전 가방 은 모든 아 이 템 을 임의로 선택 할 수 있다 는 점 이다.완전 가방 은 01 가방 과 비슷 해 완전 가방 을 01 가방 으로 전환 할 수도 있 고, 상태 이동 방정식 을 찾 을 수도 있다.
1. 완전 가방 2. 완전 가방 변형 문제 - 최소 승차 비용 3. 완전 가방 변형 문제 - 화폐 시스템
1. 완전 가방
문제 설명: n 개의 아 이 템 과 1 개의 용량 이 m 인 가방 이 있 습 니 다. 모든 아 이 템 은 무한 부품 으로 사용 할 수 있 습 니 다. 제 i 개의 아 이 템 의 부 피 는 w [i] 이 고 가 치 는 v [i] 입 니 다. 어떤 아 이 템 을 가방 에 넣 으 면 이 아 이 템 들 의 가 치 를 합 쳐 가장 크 고 가방 용량 을 초과 하지 않 는 지 알 아 보 세 요.
설명: 완전 가방 문 제 는 01 가방 문제 와 비슷 해 01 가방 문제 로 개조 할 수 있다.방법 1: 개조 상태 전이 방정식: f (n, m) = max {k * v [i] + f (i - 1, j - k * w [i])}, 그 중에서 k = 0.........................................................
* * 방법 2: * * f (n, m) = max {f (n - 1, m), f (n, m - w [n]) + v [n]}

package com.zd.dp.complete;

import java.util.ArrayList;

/**
 *       
 *  n       m   ，        ，      
 *
 */
public class Main{
    public static void main(String[] args){
        int n = 4;
        int[] weight = {2,3,4,7};
        int[] value = {1,3,5,9};
        int m = 10;
        int res = getMaxValue(n,weight,value,m);
        System.out.println(res);

        int res_01 = getMaxValue_01(n,weight,value,m);
        System.out.println(res_01);

        int res_01_new = getMaxValue_01_new(n,weight,value,m);
        System.out.println(res_01_new);
    }

    /**
     *    ：        
     * @param n
     * @param weight
     * @param value
     * @param m
     * @return
     */
    private static int getMaxValue_01_new(int n, int[] weight, int[] value, int m) {
        if (n == 0 || m == 0)
            return 0;
        int[][] dp = new int[n][m+1];
        for (int i = 0; i < m+1; i++){
            dp[0][i] = (i/weight[0])*value[0];
        }
        for (int i = 0; i < n; i++)
            dp[i][0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m + 1; j++) {
                int a = dp[i-1][j];
                int b = j-weight[i]
                        < 0 ? 0 : dp[i][j-weight[i]]+value[i];
                dp[i][j] = Math.max(a,b);
            }
        }
        return dp[n-1][m];
    }


    /**
     *    ：      
     * @param n
     * @param weight
     * @param value
     * @param m
     * @return
     */
    private static int getMaxValue(int n, int[] weight, int[] value, int m) {
        if (n == 0 || m == 0)
            return 0;

        int[][] dp = new int[n][m+1];

        //       
        for (int i = 0; i < m+1; i++){
            dp[0][i] = (i/weight[0])*value[0];
        }
        //       
        for (int i = 1; i < n; i++){
            dp[i][0] = 0;
        }

        //    ，    ，        
        for (int i = 1; i < n; i++){
            for (int j = 1; j < m+1; j++){
                int k = j/weight[i];
                for (int l = 0; l <= k; l++){
                    int temp = dp[i-1][j-l*weight[i]]+l*value[i];
                    dp[i][j] = dp[i][j] > temp ? dp[i][j] : temp;
                }
            }
        }
        return dp[n-1][m];
    }
}

2. 완전 가방 변형 문제 - 최소 승차 요금
문제 설명: 한 거리 에 1 킬로미터 마다 버스 정류장 이 있 는데 승차 비용 은 다음 과 같다. 킬로미터 수 1, 2, 3, 4, 5, 6, 8, 9 10 비용 12, 21, 31, 49, 58, 69, 79, 90 101 이 고 한 대의 자동 차 는 10 킬로 미 터 를 초과 하지 않 는 다. 어떤 사람 은 n 킬로 미 터 를 달리 고 싶다. 만약 에 그 가 임의로 차 를 갈 아 탈 수 있다 고 가정 하면 승차 방안 을 찾 아 비용 을 최소 화 해 주 십시오.
분석: 이 문 제 는 완전 가방 의 응용 으로 사람 은 임의의 곳 에서 내 려 환 승 할 수 있다.

/**
 *       
 */
public class MinCarFee {
    public static void main(String[] args){
        int[] a = {12,21,31,40,49,58,69,79,90,101};
        int n = 13;
        int res = getMinFee(a,n);
        System.out.println(res);
    }

    /**
     *       
     * @param a
     * @param n
     * @return
     */
    private static int getMinFee(int[] a, int n) {
        if (a == null || n == 0)
            return 0;
        int length = a.length;
        int[][] dp = new int[length][n+1];
        //     
        for (int i = 0; i < n+1; i++){
            dp[0][i] = i*a[0];
        }
        //     
        for (int i = 0; i < length; i++){
            dp[i][0] = 0;
        }
        //           
        for (int i = 1; i < length; i++){
            for (int j = 1; j < n+1; j++){
                int A = dp[i-1][j];
                int B = j-i-1 >= 0 ? dp[i][j-i-1]+a[i]:Integer.MAX_VALUE;
                dp[i][j] = Math.min(A,B);
            }
        }
        return dp[length-1][n];
    }
}

3. 완전 가방 변형 문제 - 화폐 시스템
문제 설명: 하나의 화폐 시스템 {1, 2, 5, 10, 20} 을 사용 하여 특정한 화폐 액면가 가 발생 할 수 있 는 방법 은 몇 가지 가 있 습 니까?
분석: f (i, j) = f (i - 1, j) + f (i, j - a [i])

/**
 *     ，        ，        
 */
public class CountsMoney {
    public static void main(String[] args){
        int[] money = {1,2,5,10,20};
        int n = 7;
        int res = getCounts(money,n);
        System.out.println(res);
    }

    /**
     *        
     * @param money
     * @param n
     * @return
     */
    private static int getCounts(int[] money, int n) {
        if (money == null || n == 0)
            return 0;
        int length = money.length;
        int[][] dp = new int[length][n+1];
        //     
        for (int i = 0; i < n+1; i++)
            dp[0][i] = 1;

        //     
        for (int i = 0; i < length; i++)
            dp[i][0] = 0;

        //      
        for (int i = 1; i < length; i++)
            for (int j = 1; j < n+1; j++){
                int A = dp[i-1][j];
                int B = j - money[i] >= 0 ? (dp[i][j-money[i]]==0?1:dp[i][j-money[i]]) : 0;
                dp[i][j] = A + B;
            }
        return dp[length-1][n];
    }
}

결론: 상태 전이 방정식 을 확정 할 수 없 을 때 2 차원 배열 을 그 려 서 배열 을 채 워 서 규칙 을 찾 아 보 는 것 도 좋 습 니 다.상기 코드 공간 은 복잡 도가 비교적 높 고 최적화 방식 은 2 차원 배열 을 1 차원 배열 로 바 꿀 수 있다.