[DP] 0/1 Knapsack

0/1 knapsack, 배낭채우기 문제는 DP에서 유명한 문제 중 하나이다.

1) N개의 물건에 각각 무게 정보와 가치 정보가 주어지고

2) W의 무게까지 담을 수 있는 가방이 있을 때, 

3) 가방의 가치를 가장 높게 만들어 줄 물건들을 담아야 한다.

 

보통은 도둑이 물건을 훔쳐갈 때, 들고갈 수 있는 무게는 제한적이니 그런 것들을 이용해서 알고리즘 문제가 나오더라.

하지만 오늘은 특정 문제를 포스팅 하는게 아니라, 알고리즘 자체를 올려보려고 한다.

 

이 알고리즘의 로직은

1) 첫 물건부터 끝 물건까지, 가방의 무게를 1부터 W까지 모두 고려해서

2) 물건의 무게가 현재 가방의 무게보다 작거나, 같으면 넣어본다.

  2-1) 이번 아이템을 넣지 않았을 때와, 넣었을 때를 비교해서 더 큰 값을 저장해주는 방식이다.

3) 만약 물건의 무게가 현재 가방의 무게보다 크다면 이전 상태를 가져간다. 

 

저 로직을 실행하기 위해 N*W 사이즈의 배열이 하나 더 필요하다.

for문이 다 돌고 나면, (N,W) 자리의 값이 우리가 원하는 값이 된다.

 

package ex_0325;

import java.util.Arrays;
import java.util.Scanner;

public class Knapsack {
	//0-1 Knapsack
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); //물건의 개수
		int W = sc.nextInt(); //가방의 무게
		
		int[] weights = new int[N+1]; //물건의 무게정보
		int[] profits = new int[N+1]; //물건의 가치정보
		int[][] D = new int[N+1][W+1]; //해당 물건까지 고려하여 해당 무게를 만들 떄 까지 최대 가치
		
		
		for(int i=1; i<N+1; i++) { //물건이 0개일 때도 고려하기 위해 0은 0으로.
			weights[i] = sc.nextInt();
			profits[i] = sc.nextInt();
		}
		
		for(int i=1; i<N+1; i++) { //첫 물건부터 끝 물건까지.
			for(int w=1; w<W+1; w++) {//가방의 무게 1부터 W까지 모두 고려.
				if(weights[i] <= w) { 
					//물건의 무게가 현재 가방의 무게보다 작거나 같으면 넣어보기.
					//i-1아이템까지 넣은 가방에 이번꺼 넣어보기 vs 직전꺼 그대로 들고가기
					D[i][w] = Math.max(D[i-1][w-weights[i]]+profits[i], D[i-1][w]);
					
				}else { //가방에 넣지 못하는 상황.
					//이번 물건이 가방 무게보다 무거우니까 직전 무게까지의 최적이 지금 최적 해
					D[i][w] = D[i-1][w]; 
				}
			}
		}
		
		System.out.println(Arrays.toString(weights));
		System.out.println(Arrays.toString(profits));
		//최종. 가방 무게까지 모든 아이템 고려.
		System.out.println(D[N][W]);
	}
}