백준 12865번: 평범한 배낭 (C++)

 

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

 

 

 

다이나믹 프로그래밍 문제이다. (knapsack 문제) 

 

 

 

<전체적인 알고리즘>

1. 특정 아이템을 넣을지 말지의 경우를 모두 저장하며 구해나간다.

    - 아이템 마다 결정할 때 가방의 무게가 w ~ k일 때의 모든 경우를 저장하여야 한다.

       (w미만은 어차피 넣을 수 없으니 고려할 필요가 없음)

2. 마지막 아이템까지 다이나믹 프로그래밍을 진행하면 결국 가방 무게가 k일때의 d[k]값이 정답이다.

 

 

 

<부가적 설명>

- knapsack문제를 2차원 배열에 저장하며 계산한다면 좀 더 이해하기 직관적일 것이다. 하지만 메모리를 아끼기 위해 1차원 배열로 알고리즘을 구현하였다.

- 1차원 배열을 이용한다면 배열을 계속 갱신할 때 뒤에서 부터 갱신하여야 한다. 뒤에서 부터 갱신하여야 그 전의 값들을 사용할 수 있기 때문이다.

 

 

 

<전체 코드>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

#include<iostream> #include<algorithm>   using namespace std;   int item[102][2]; // 0 -무게 / 1- 가치 int d[100002];   int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);       int n, k;     cin >> n >> k;       for (int i = 0; i < n; i++)     {         int w, v;         cin >> w >> v;       //각 아이템의 무게와 가치 입력                   for (int j = k; j >=w; j--)  // 가방 용량이 w ~ k 인 경우 전부 구하기         {             d[j] = max(d[j - w] + v, d[j]);  //item을 넣었을 때와 넣지 않은 것중 가치 큰 값 저장         }     }       cout << d[k];  // 가방무게가 k일 때 가치의 최대 값       return 0; }

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.