01 가방, 완전 가방, 다 중 가방 템 플 릿

세 가지 가방 개념
01 가방 (ZeroOne Pack): N 개의 아 이 템 과 V 용량 의 가방 이 있 습 니 다.모든 물건 은 하나 밖 에 없다.제 i 물품 의 비용 은 c [i] 이 고 가 치 는 w [i] 입 니 다.어떤 물건 을 가방 에 넣 으 면 가 치 를 총화 할 수 있 는 지 알 아 보 세 요.완전 가방 (Complete Pack): N 가지 아 이 템 과 V 용량 의 가방 이 있 으 며, 모든 아 이 템 은 무한 정 사용 가능 합 니 다.제 i 종 물품 의 비용 은 c [i] 이 고 가 치 는 w [i] 입 니 다.어떤 물건 을 가방 에 넣 으 면 이 물건 들 의 비용 을 합 쳐 가방 용량 을 초과 하지 않 고 가치 가 가장 큰 지 알 아 보 세 요.다 중 가방 (Multiple Pack): N 가지 아 이 템 과 V 용량 의 가방 이 있 습 니 다.제 i 종 아 이 템 은 최대 n [i] 개 를 사용 할 수 있 습 니 다. 모든 비용 은 c [i] 이 고 가 치 는 w [i] 입 니 다.어떤 물건 을 가방 에 넣 으 면 이 물건 들 의 비용 을 합 쳐 가방 용량 을 초과 하지 않 고 가치 가 가장 큰 지 알 아 보 세 요.
이 세 가지 가방 문제 의 차 이 는 01 가방 은 각 아 이 템 만 한 개 만 들 수 있 고 완전 가방 은 각 아 이 템 을 몇 번 도 들 수 있 으 며 다 중 가방 은 각 아 이 템 을 제한 적 으로 들 수 있다 는 것 이다.
템 플 릿

01 가방 용량: V 아 이 템 종류: N 아 이 템 이 차지 하 는 공간 (비용): c [N] 아 이 템 가치: w [i]

여기 dp[i][v] 는 앞의 i 개 상품 에 v 용량 의 가방 에 넣 으 면 얻 을 수 있 는 최대 가치 입 니 다.제 i 건 상품 에 대해 서 는 제 i 건 상품 을 찾 거나 찾 지 않 는 두 가지 상황 이 있 습 니 다.상품 수령 에 대해 dp[i][v]=dp[i-1][v-c[i]]+w[i] 현재 의 최대 가 치 는 앞의 i - 1 개 아 이 템 을 v - c [i] 의 가방 에 넣 으 면 얻 을 수 있 는 최대 가치 에 현재 아 이 템 의 가 치 를 더 한 것 과 같다.한편, 상품 을 찾 지 않 는 경우 dp[i][v]=dp[i-1][v], 즉 현재 최대 가 치 는 앞의 i - 1 개 상품 을 취하 여 용량 이 v 인 가방 에 넣 는 것 과 같다.상태 전이 방정식 은 다음 과 같다.

dp[i][V] = Math.max(dp[i-1][V],dp[i-1][v-c[i]]+w[i]);

상기 이전 방법 을 간소화 하기 위해 순환 할 때 물품 종 류 를 외곽 으로 하고 가방 용량 을 안쪽 으로 하 며 V 에서 0 으로 간략화 한다.

dp[V] = Math.max(dp[V],dp[v-c[i]]+w[i]);

템 플 릿 은 다음 과 같 습 니 다:

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int N = sc.nextInt(); //    
            int V = sc.nextInt(); //    
            int[] c = new int[N]; //       （    ）
            int[] w = new int[N]; //       
            for (int i = 0; i < N; i++) {
                c[i] = sc.nextInt();
                w[i] = sc.nextInt();
            }

            int[] dp = new int[V + 1];
            for (int i = 0; i < N; i++) {
                for (int j = V; j >= 1; j--) {
                    if (c[i] <= j) {
                        dp[j] = Math.max(dp[j], dp[j - c[i]] + w[i]);
                    }
                }
            }

            System.out.println(dp[V]);
        }
    }
}

완전 가방 용량: V 아 이 템 종류: N 아 이 템 이 차지 하 는 공간 (비용): c [N] 아 이 템 가치: w [i] 이런 문제 의 특징 은 한 아 이 템 을 수 차례 받 을 수 있다 는 것 이다.여기 서 현재 아 이 템 i 가 k 회 를 가 져 갔다 고 가정 하면 k 의 범 위 는 0 < = k * c [i] < = v 이 고 여기 0 은 가 져 가지 않 는 다 는 뜻 입 니 다.동적 전이 방정식 은 다음 과 같다.

dp[i][v] = Math.max(dp[i-1][v-k*c[i]]+k*w[i]) ，  0 <= k * c[i] <= v

1 차원 배열 로 전환: 여기 와 01 가방 의 차 이 는 내부 순환 순서 입 니 다.

for i : 0...N
	for j : 1...V
		dp[v] = Math.max(dp[v],dp[v-c[i]]+w[i]) ，  0 <= k * c[i] <= v

템 플 릿 은 다음 과 같 습 니 다:

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int N = sc.nextInt(); //    
            int V = sc.nextInt(); //    
            int[] c = new int[N]; //       （    ）
            int[] w = new int[N]; //       
            for (int i = 0; i < N; i++) {
                c[i] = sc.nextInt();
                w[i] = sc.nextInt();
            }

            int[] dp = new int[V + 1];
            for (int i = 0; i < N; i++) {
                for (int j = 1; j <= V; j++) {
                    if (c[i] <= j) {
                        dp[j] = Math.max(dp[j], dp[j - c[i]] + w[i]);
                    }
                }
            }

            System.out.println(dp[V]);
        }
    }
}

멀 티 백 팩 은 N 가지 아 이 템 과 V 용량 의 백 팩 이 있다.제 i 종 아 이 템 은 최대 n [i] 개 를 사용 할 수 있 습 니 다. 모든 비용 은 c [i] 이 고 가 치 는 w [i] 입 니 다.어떤 물건 을 가방 에 넣 으 면 이 물건 들 의 비용 을 합 쳐 가방 용량 을 초과 하지 않 고 가치 가 가장 큰 지 알 아 보 세 요.그 상태 전이 방정식 은 완전 가방 과 유사 하 다. i 번 째 아 이 템 은 n [i] 건 이 있 기 때문에 모두 n [i] + 1 가지 전략, 즉 0 건, 1 건... n [j] 건 을 취하 고 상태 전이 방정식 은 다음 과 같다.

dp[i][v] = Math.max(dp[i-1][v-k*c[i]]+k*w[i]) (0 <= k <= n[i])

초기 화 조건:

dp[i][0] = 0;
dp[0][v] = 0

가방 용량: V 아 이 템 종류: N 아 이 템 종류 설정: Goods 아 이 템 배열: goods []

class Goods{
    private int count;//     
    private int cost;//     
    private int worth;//     
}

총 3 층 순환:

for i 0 ... N
   for j 1....V
   		for k 0...goods[i].count
   			dp[i][j] = Math.max(dp[i][j],dp[i-1][v-k*goods[i].cost]+k*goods[i].worth);

템 플 릿 은 다음 과 같 습 니 다:

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int N = sc.nextInt(); //    
            int V = sc.nextInt(); //    
            Goods[] goods = new Goods[N];
            for (int i = 0; i < N; i++) {
                goods[i] = new Goods(sc.nextInt(), sc.nextInt(), sc.nextInt());
            }

            int[][] dp = new int[N][V + 1];


            for (int i = 0; i < N; i++) {
                for (int j = 1; j <= V; j++) {
                    for (int k = 0; k < goods[i].getCount(); k++) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * goods[i].getCost()] + k * goods[i].getWorth());
                    }
                }
            }

            System.out.println(dp[N - 1][V]);
        }
    }
}