[코딩테스트][Java] 백준 12865, 평범한 배낭

문제

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

접근

집합 A를 N개의 물건들 중 배낭이 버틸 수 있는 무게 K의 범위 내에서 넣을 수 있는 가치의 최댓값을 이루는 집합이라고 가정합니다.

1. 집합 A에 N번째 물건을 포함하지 않는 경우
   • A는 N번째 물건을 뺀 나머지 N-1개의 물건들 중에서 최적으로 고른 부분집합과 같습니다.
2. 집합 A에 N번째 물건을 포함하는 경우
   • A에 속한 물건들의 가치 합계는 N번째 물건의 가치 + N-1개의 물건들 중에서 최적으로 고른 가치의 합계입니다.

위 경우들을 점화식으로 구성하면 다음과 같습니다.

• V[i,w] : i개의 물건들 중에서 배낭에 담을 수 있는 최대 무게가 w일때 가치의 최대값을 의미함. 예를 들어 V[4,7]이면 4개의 물건들중에서 배낭의 최대 무게가 7일때 나올 수 있는 가치의 최댓값을 의미함.
• V[i-1,w] if weight_i > w : 만약 물건들의 무게들을 저장하는 weight 배열의 i번째 물건의 무게가 w보다 큰 경우 i번째 물건은 배낭에 담을 수 없기 때문에 i-1개의 물건들 중에서 가치의 최대값을 탐색합니다.
• max{value_i + V[i-1,w-weight_i], V[i-1,w]} else : weight 배열의 i번째 물건의 무게가 최대 무게인 w보다 작다면 배낭에 담을 수 있으므로 두가지 케이스 중에서 더 큰 가치값을 V[i,w]에 저장합니다.
  1. i번째 물건을 배낭에 넣고 가치의 최대값을 탐색 ( value_i + V[i-1,w-weight_i] )
  2. 배낭에는 넣을 수 있는 무게이지만 i번째 물건을 배낭에 넣지 않고 i-1개의 물건만으로 가치의 최대값을 탐색

위 점화식을 코드로 구현하면 다음과 같습니다.

if(weight[i]<=w)
{
	if(value[i]+V[i-1][w-weight[i]] >= V[i-1][w])
	{
		V[i][w] = value[i]+V[i-1][w-weight[i]];
	}
	else
	{
		V[i][w] = V[i-1][w];
	}
}
else
{
	V[i][w] = V[i-1][w];
}

 

Dynamic Programming 방식의 수행과정

위 수행과정에서 V[4][7] 위치의 값의 의미는 4개의 물건중에서 배낭의 최대 무게가 7인 상태에서 나올 수 있는 가치의 최대값을 의미합니다. V[4][7]을 계산하기 위해서 두가지를 비교합니다.

• 첫번째 경우 : 4번째 물건을 배낭에 넣지 않고 나머지 3개의 물건만으로 배낭에 넣어 나오는 가치의 최대값,        V[3][7] = 14
• 두번째 경우 : 4번째 물건을 배낭에 포함하여 나올 수 있는 가치의 최대값, value[4] + V[3][2] = 12 + 0 = 12

두 경우중 V[3][7]이 더 크므로 V[4][7]=14가 됩니다.

 

Java언어 기반 Dynamic Programming 방식 구현

public class Main {
	
	public static int solution(int n, int k, int[] weight, int[] value)
	{
		int[][] V = new int[n+1][k+1];
		
		for(int i=1;i<=n;i++)
		{
			for(int w=1; w<=k; w++)
			{
				if(weight[i]<=w)
				{
					if(value[i]+V[i-1][w-weight[i]] >= V[i-1][w])
					{
						V[i][w] = value[i]+V[i-1][w-weight[i]];
					}
					else
					{
						V[i][w] = V[i-1][w];
					}
				}
				else
				{
					V[i][w] = V[i-1][w];
				}
			}
		}
		
		return V[n][k];
	}
		
	public static void main(String args[]) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str[] = br.readLine().split(" ");
		int n = Integer.parseInt(str[0]);
		int k = Integer.parseInt(str[1]);
		int[] weight = new int[n+1];
		int[] value = new int[n+1];
		
		for(int i=1;i<=n;i++)
		{
			str = br.readLine().split(" ");
			weight[i] = Integer.parseInt(str[0]);
			value[i] = Integer.parseInt(str[1]);
		}
		System.out.println(solution(n,k,weight,value));
		
	}
}

 

Memoization 방식의 구현

public class Main2 {
	public static int[][] dp;
	public static int n;
	public static int k;
	public static int[] weight;
	public static int[] value;
	
	public static int solution2(int i, int w)
	{
		if(i==0)
		{
			return 0;
		}
		
		if(weight[i]<=w)
		{
			if(dp[i-1][w-weight[i]]==0)
			{
				dp[i-1][w-weight[i]] = solution2(i-1,w-weight[i]);
			}
			if(dp[i-1][w]==0)
			{
				dp[i-1][w] = solution2(i-1,w);
			}
			
			return dp[i][w] = Math.max(value[i]+dp[i-1][w-weight[i]], 
							dp[i-1][w]);
		}
		else
		{
			if(dp[i-1][w]==0)
			{
				return dp[i][w] = solution2(i-1,w);
			}
			else
			{
				return dp[i][w] = dp[i-1][w];
			}
		}
	}
	
	public static void main(String args[]) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str[] = br.readLine().split(" ");
		n = Integer.parseInt(str[0]);
		k = Integer.parseInt(str[1]);
		dp = new int[n+1][k+1];
		weight = new int[n+1];
		value = new int[n+1];
		
		for(int i=1;i<=n;i++)
		{
			str = br.readLine().split(" ");
			weight[i] = Integer.parseInt(str[0]);
			value[i] = Integer.parseInt(str[1]);
		}
		System.out.println(solution2(n,k));
		
	}
}

 

References

https://gsmesie692.tistory.com/113