백준 12865번 [평범한 배낭](C++)-yes6686- 티스토리

백준 문제 풀이: 12865 [평범한 배낭]

---

문제 링크: https://www.acmicpc.net/problem/12865

문제 설명:

n개의 물건이 있고, 각 물건은 무게와 가치가 있습니다. 최대 k 무게를 담을 수 있는 배낭에 물건을 담을 때, 최대 가치를 구하는 문제입니다.

입력:

• 첫째 줄에 정수 n (1 ≤ n ≤ 100)과 k (1 ≤ k ≤ 100,000)이 주어집니다.
• 다음 n개의 줄에는 각각 물건의 무게 w (1 ≤ w ≤ k)와 가치 v (0 ≤ v ≤ 1,000)가 주어집니다.

출력:

• 첫째 줄에 배낭에 담을 수 있는 물건들의 가치합의 최댓값을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

int n, k;
int weight[101];
int value[101];
int dp[101][100001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;

    for (int i = 1; i <= n; i++) {
        cin >> weight[i] >> value[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= k; w++) {
            if (weight[i] > w) {
                dp[i][w] = dp[i - 1][w]; // 물건을 담지 못하는 경우
            } else {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight[i]] + value[i]); // 담거나 담지 않는 경우 비교
            }
        }
    }

    cout << dp[n][k] << '\n'; // 최댓값 출력
    return 0;
}

예제

입력:
4 7
6 13
4 8
3 6
5 12

출력:
14

---

코드 설명

• 다이나믹 프로그래밍:
  • dp[i][w]는 i번째 물건까지 고려하고, 배낭의 현재 무게가 w일 때의 최대 가치를 저장합니다.
  • 현재 물건의 무게가 배낭의 남은 용량을 초과하면, 이전 상태를 그대로 가져옵니다.
  • 현재 물건을 담거나 담지 않는 경우 중 최댓값을 선택합니다.

시간 복잡도

• n개의 물건에 대해 k의 무게까지 반복하므로 O(n * k)의 시간 복잡도를 가집니다.
• n ≤ 100, k ≤ 100,000이므로 충분히 처리 가능합니다.

---

결과

코드는 주어진 배낭 문제를 정확히 해결하며, 동적 프로그래밍을 활용한 효율적인 구현입니다. 입력 크기에 맞게 최적화되어 있어 실용적입니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!