[12865] 평범한 배낭 - c++

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

12865번: 평범한 배낭

진짜 너 어어어ㅓㅇ무 어려웠다 답을 보면서도 이게 왜? 대체 왜? 라는 생각이 끊이질 않았다.

이러한 문제를 KnapSack Problem(배낭 채우기 문제)라고 말한다.

 

---

풀이

일단 다이나믹 프로그래밍을 사용해서 풀어야 된다.

(진짜 정말 어떻게 이걸 다이내믹 프로그래밍으로 테이블을 정의해서 풀어낼 생각을 한 걸까? 미친 걸까? 대단하다.)

 

어렵다고 포기하지 말라
- 정훈 -

1) 만약 선택한 물건의 무게가 배낭의 임시 용량을 초과 한다면?

• 전에 있던 최댓값을 그대로 가져온다 (지금 말이 좀 어렵지만 이따 그림을 보면서 다시 설명하겠다)

2) 만약 선택한 물건의 무게가 배낭의 임시 용량을 초과하지 않는 다면? (즉 적정 범위 안에 다 들어간다면?)

• 전에 있던 최댓값과 [임시 무게 - 물건의 무게] 둘 중에 큰 것을 고른다.

점화식

w[i] 는 현재 선택한 물건의 무게 j는 가방의 임시 무게

 

 

나중에 내가 이해할 수 있도록 최대한 자세하게 그림을 그려 보아야겠다.

가방에 무게 0짜리 물건만 들어올 수 있는 첫 번째 열은 0으로 초기화 

dp [1][6] = max(dp [i - 1][ j ], dp[i - 1][ j-w [ i ] ] + v [ i ])

= max(0, dp [i-1][6-6] + 13)

= max(0, 13)

= 13

dp [2][6] = max(dp [i - 1][ j ], dp[i - 1][ j-w [ i ] ] + v [ i ])

= max(13, dp [2-1][6-4] + 8)

= max(13, dp [1][2] + 8)

= max(13,8)

= 13

dp [3][5] = max(dp [i - 1][ j ], dp[i - 1][ j-w [ i ] ] + v [ i ])

=max(13, dp [3-1][5-1] + 8)

=max(8, dp [2][4] + 20)

= max(8, 28)

= 28

---

CODE

#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int n, k;

//w = 무게, v = 가치
int w[101], v[101];
int dp[101][100'005];

int main(){
  init();
  cin >> n >> k;
  for(int i = 1; i <= n; ++i) cin >> w[i] >> v[i];

  for(int i = 1; i <=n; ++i){
    for(int j = 1; j <= k; ++j){
      // w[i] > j (현재 물건의 무게가 임시 무게보다 크다면 즉 초과 된다면)
      if(w[i] > j)
        dp[i][j] = dp[i-1][j];
      // w[i] <= j (현재 무게가 수용 가능한 무게보다 작거나 같을 때) 
      else
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
    }
  }
  cout << dp[n][k];
  return 0;
}

---

문제를 풀며

정말 어려웠다

DP문제라서 더 어렵다고 느껴졌다.

답을 봐도 어려웠고

새로운 아이디어를 얻을 수 있었다 

이렇게도 풀 수가 있네....