[백준 12865번] - 평범한 배낭(C/C++)

12865번: 평범한 배낭

[문제 설명]

---

[문제 풀이]

다이나믹 프로그래밍 문제 중 유명한 유형인  Knapsack Problem(배낭 문제)이다.

물건들은 각각 무게(W)와 가치(V)를 가지고 있다.

배낭에 넣을수 있는 무게의 한계(K)가 정해져있고, 무게 한도 안에서 넣을수있는 물건들(N)의 가치합의 최댓값을 구하면 된다.

 

물건들을 처음부터 차례로 확인한다.

2차원 배열 dp를 선언하여 dp[물건 인덱스][무게]의 가치의 최대값을 저장하기 위해 사용한다.

 

반복문(j)을 통해 무게를 1부터 K까지 확인한다. 각 무게별로 가치의 최대값을 계속해서 저장해나가면서 최대값을 구한다.

 

현재 물건을 넣는경우와 넣지 않는 경우 2가지가 있다. 

 

1. 넣는 경우는 현재 물건의 무게(W)가 현재 확인하고 있는 무게 한도(j)보다 작다면, 이전까지 확인한 최대값 중 dp[i-1][j-W]인 값에 현재 V를 더하여 dp[i][j]에 저장한다. 

 

2. 1번에서 구한 dp[i][j]값과 dp[i-1][j]의 값을 비교해서 더 큰 값을 dp[i][j]에 넣어준다. dp[i-1][j]를 dp[i][j]에 넣는것은 현재 물건을 배낭에 넣지 않는 경우이다.

 

모든 물건을 확인할때까지 1번과 2번 과정을 반복한다.

 

dp[N][K]의 값을 출력하면 된다.

파이팅 !

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

#include <bits/stdc++.h>
using namespace std;

int dp[101][100001];
int weights[101];
int values[101];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n,k;
    cin >> n >> k;
    for(int i =1 ; i <= n; i++)
    {
        cin >> weights[i];
        cin >> values[i];
    }

    for(int i =1; i <= n; i++)
    {
        for(int j = 1; j <= k; j++)
        {
            if(weights[i] <= j)
            {
                dp[i][j] = dp[i-1][j-weights[i]] + values[i];
            }

            dp[i][j] = max(dp[i][j], dp[i-1][j]);
        }
    }
    cout << dp[n][k] << "\n";
}