[백준] 12865번 : 평범한 배낭 - C++ / JAVA

백준 12865 : 평범한 배낭

등급 : Gold V

12865번: 평범한 배낭 (acmicpc.net)

12865번: 평범한 배낭

사용 알고리즘 : Dynamic Programming

사용 자료구조 : Vector

 

고전적인 다이나믹 프로그래밍 문제, 0-1 배낭(Knapsack) 문제이다.

배낭 하나에 가치가 최대가 되도록 물건을 넣는 문제.

 

배열에 물건의 무게와 가치를 저장하고, 그에 따른 DP테이블을 생성한다.

0번 인덱스를 사용해야 하기 때문에, 테이블은 (물건의 갯수 + 1) × (최대 수용 무게 + 1)로 생성한다.

첫 번째 물건부터, 무게를 쭉 비교하며 가능한 위치에 가치를 입력한다.

두 번째 물건도 동일하게 진행해주되, 이전 물건의 무게와 비교하여 더 큰 값을 입력한다.

 → 무게가  j일 때 넣을 수 있는 최대치를 구하는 것이므로, 이전과 비교해 이전이 더 크면 그 값을 따른다.

세 번째 물건도 동일하게 진행해준다.

이때, 물건의 무게가 3이므로, 두 번째까지 고려해준 가방의 무게 4(dp[2][4])에 이 물건을 더해줄 수 있다.

 → 두 번째 물건에서 무게 4를, 세 번째 물건에서 무게 3을 더해 무게 7일 때 14가 되는 것.

 → 사실 이전까지의 과정에서도 이와 같은 방법으로 진행되었다. (0이기에 고려되지 않은 것처럼 보였던 것)

모두 진행하게 되면 이와 같은 표가 만들어지며, DP테이블의 가장 마지막 값이 구하고자 하는 최댓값이 된다.

위의 과정에서 무게를 구하는 방법을 점화식으로 나타내면 DP[i][j] = max(DP[i-1][j], DP[i-1][j-weight[i]] + value[i])

<hide/>
#include <iostream>
#include <vector>

using namespace std;

int dp[101][100001] = { 0 };

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;
    vector <pair <int, int>> v;
    v.resize(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i].first >> v[i].second;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            if (v[i].first <= j)
            {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i].first] + v[i].second);
            }
            else dp[i][j] = dp[i - 1][j];
        }
    }
    cout << dp[n][k];
}

<hide/>
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[] weight = new int[n+1];
        int[] value = new int[n+1];
        int[][] dp = new int[n+1][k+1];
        for(int i=1; i<=n; i++)
        {
            st = new StringTokenizer(br.readLine());
            weight[i] = Integer.parseInt(st.nextToken());
            value[i] = Integer.parseInt(st.nextToken());
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=k; j++)
            {
                if(j >= weight[i])
                {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);
                }
                else dp[i][j] = dp[i-1][j];
            }
        }
        System.out.println(dp[n][k]);
    }
}