Dynamic Programing 3

냅색 DP 푸는 방식
1) 냅색 문제 확인
a. (0/1 문제) 더 이상 쪼갤수 없는 N개의 물건들을 조합을 해서, 특정 수 M값을 만들었을때, 선택된 물건들의 값을 구하여라.
i. 물건들의 값  :  최대가치, 최소가치, 개수, 만들수 있는 수인지 아닌지( 1 or 0 )
ii. 만들려는 수 :  총 가방의 무게, 확인하고 싶은 구슬의 무게, Limits
iii. 0/1 문제
- 선택하거나 선택하지 않거나 문제
- 선택하는 것들을 여러가지 경우로 나눌수 있으면 조건에 따라 Dp Update 복수개.
□ 조건에 따라 적재되는 예제들..
- 선택하는 것들을 여러가지 경우로 쪼갤수 없으면 dp 파라메터로 추가.
b. 물건을 쪼갤수 없고, 가방에 넣을 수 있으면 냅색.
i. 물건을 쪼갤수 있거나, 하나만 들어갈수 있으면 그리디
ii. 항상 최적의 해만 고려했을때 풀수 있음.
c. 물건의 개수(N) * 가방의 무게(M) <= 1억 이하
i. Default 냅색 문제 N = 10만, M = 100
ii. N 백만이상 인 경우, N을 줄이는 알고리즘 적용 (grouping)
iii. 1억 byte = 약 100MB, 인덱스 날리는 최적화 메모리 진행.

2) 냅색 문제의 종류
a. 특정 숫자를 만들수 있는지 없는지 여부를 묻는 문제
ii. 기저조건 있음.
1)

b. 최대값 최소값 구하는 문제
i. 대표 문제
1) 동전, 가방에 물건 넣을때 최대, 최소 가치
ii. 기저조건 없음.

3) 점화식 정의 및 설계
- Dp[i][k] =  i번째 까지 물건 고려, 가방의 무게가 k일때 최대 가치.
○ i 번째 물건을 선택하는 경우,  이전 물건에 선택한 경우에서 현재 물건의 가치를 더한 값.
○ i 번째 물건을 선택하지 않는 경우, 이전 물건의 선택했을때 최대가치
- 기저 조건
○ dp 값이 가치 최대, 최소의 경우
§ 기저조건 필요 없는 경우
○ 무게 j를 만들수 있는가의 경우,  || 방법의 개수
§ 무게 0을 만드는 방법은 물건을 고려하지 않는 경우 (i==0)이기 때문에
§ For (int i=1; i<=N; i++) dp[i][0]  = 1;

3) 냅색 고려할점 
- 냅색 물건 선택 유형
a. 물건 중복 안되는 경우 max(dp[i-1][j], dp[i - 1][j - K[i]]);
b. 물건 중복 가능한 경우 max(dp[i-1][j], dp[i][j - K[i]]);

- DP 메모리 줄이기
○ 2차원에서 1차원을 바꿀수 있음.
§ 1차원 변경시 역추적 알고리즘 진행시 제대로 동작하지 않을 수 있음.
○ 1차원 변경시 중복이 가능한 경우는 순차 탐색이 가능하지만, 중복이 가능하지 않으면 역 탐색을 사용해야 함.
○ K 배열 : 물건 무게, T 배열 : 가치, L : 가방 무게
○ 중복 선택 허용시 순방향 탐색

int dp[20 * 1001];
for (int i = 1; i <= N; i++) {
  for (int j = 0; j <= L; j++) {
    if (j - K[i] >= 0) dp[j] = max(dp[j], dp[j - K[i]] + T[i]); 
  }
}

○ 중복 선택 안될 경우, 역방향 탐색
§ 물건을 선택하지 않은 경우도 자동으로 갱신됨.

int dp[20 * 1001];
for (int i = 1; i <= N; i++) {
  for (int j = L; j >= K[i]; j--) {
    if (j - K[i] >= 0) dp[j] = max(dp[j], dp[j - K[i]] + T[i]); 
  }
}

4) DP 테이블 검산
- 만들려는 수 K가 너무 큰 경우, 너무 많은 값이 나온다. K/10을 해서 디버깅을 하자.

문제 푸는 방식
1) 냅색 문제 확인
2) 냅색 문제의 종류 (특정값 만드는, 최대/최소)
3) 점화식 설계 (점화식, 기저조건)
4) 냅색 물건 고려할점
5) DP 테이블 검산

1) 평범한 배낭
https://www.acmicpc.net/problem/12865
N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 (가방) K (1 ≤ K ≤ 100,000)
준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

1) 냅색 문제 확인
- 물건들을 조합해서, 배낭 무게에 맞췄을때, 그때의 물건 가치의 최대값.
- 물건을 쪼갤수 없다.
- N * M(K) = 100 * 100,000 <= 1억
- 물건 중복해서 사용할수 없다.
2) 최대 / 최소
4) 물건 중복 X
4) 점화식 정의 설계
- 점화식 정의 dp[i][j] = i번째 까지 물건 고려, 가방의 무게가 j일때 최대 값, 냅색
int dp[101][100001]; 
for (int i=1; i<=N; i++) {
        for (int j=1; j<=K; j++) {
            dp[i][j] = dp[i-1][j];
            if (j - w[i] >= 0) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
          }
     }
}

5) DP 테이블 검산
0 0 0 0 0 13 13
0 0 0 8 8 13 13
0 0 6 8 8 13 14
0 0 6 8 12 13 14

파랑 1) max(dp[2][7 - 3] + 6, dp[2][7]) = max (8+6, 13) = 14
빨강 2) max(dp[3][5 - 5] + 12, dp[3][5]) = max(12, 8) = 12
빨강 3) max(dp[3][7 - 5] + 12 , dp[3][7]) = max(12, 14) = 14 


2) 보석도둑
https://www.acmicpc.net/problem/1202
N과 K가 주어진다. (1 ≤ N, K ≤ 300,000), C <= 100,000,000
세계적인 도둑 상덕이는 보석점을 털기로 결심했다.
상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 
상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 
가방에는 최대 한 개의 보석만 넣을 수 있다. 상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

1) 냅색문제 확인)
- 보석들을 조합해서, 가방 무게C에 맞췄을때, 그때의 물건 가치의 최대값.
- 가방에 하나만 들어간다. 항상 가방에 들어갈수 있는 최고의 가격의 보석만 넣으면 될듯 ?
- N * M(K) = 300,000 * 100,000,000 >= 1억 이상
--> 냅색 문제 아님

최적의 답 : 가장 가치가 좋은 보석부터 넣되, 최대한 가방에 담을수 있는 무게가 작은것 부터 넣자.
Set <중복미허용>, mlutiset <중복허용>
lower_bound : 찾으려는 key 값보다 같거나 큰 숫자가 처음 나올때를 찾을수 있음.

 

Code >
multiset<int> c;
c.insert(가방무게);…
sort(jw.begin(), jw.end(), jwCompare);
for (int i = 0; i < N; i++) {
auto it = c.lower_bound(jw[i].m); // 보석 무게
if (it != c.end()) {
ans += jw[i].v;
c.erase(it);
}
}

3) 동전
https://www.acmicpc.net/problem/9084
동전의 가지 수 N(1 ≤ N ≤ 20)
금액 M(1 ≤ M ≤ 10000)
우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 
그 방법도 여러 가지가 있을 수 있다. 
예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다.
동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.
<하양식 백트랙킹 푸는것 가능 할듯>

1) 냅색문제 확인
- 동전 조합의 경우에 있어서 주어진 금액(가방의 무게)을 딱 맞췄을때, 방법의 개수.
- 동전 쪼갤수 없고 주어진 금액을 만들기 위해 여러 개 동전 사용.
- 20 * 10000 <= 1억
2) 최대/ 최소
3) 점화식 설계 및 정의
- Dp[i][j] = i번째 동전 고려, j 원을 만들었을때 방법의 개수
DP 2차원으로 풀기

int dp[21][10010];
for (int i = 0; i <= N; i++) dp[i][0] = 1;
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= K; j++) {
dp[i][j] = dp[i - 1][j];
if (j - S[i] >= 0) {
dp[i][j] += dp[i][j - S[i]];
}
}
}
ans = dp[N][K];

DP 1차원으로 풀기

int dp[10010];
for (int i = 1; i <= N; i++) {
  for (int j = 0; j <= K; j++) {
     if (j - S[i] >= 0) {
dp[j] += dp[j - S[i]];
       }
    }
}

4) 물건 중복 되는 경우
5) DP 테이블
- 예제 : N = 2 물건 = { 5 7 }  K = 15
1차원
- 1 0 0 0 0 1 0 1 0 0 1 0 1 0 1 1
2차원
- 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
- 1 0 0 0 0 1 0 1 0 0 1 0 1 0 1 1

추가질문) 동전이 중복 가능하지 않는다면 1차원 코드를 작성해보자?
int dp[10010];
for (int i = 1; i <= N; i++) {
  for (int j = K; j  >= S[i]; j--) {
     if (j - S[i] >= 0) {
dp[j] += dp[j - S[i]];
       }
    }
}

4) 저울
https://www.acmicpc.net/problem/2629
N <= 30, 추의무게 <= 500, 확인하고자 하는 구슬의 무게는 <= 40,000
양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다.
무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다.
추들의 무게와 확인할 구슬들의 무게가 입력되었을 때, 주어진 추만을 사용하여 구슬의 무게를 확인 할 수 있는지를 결정하는 프로그램을 작성하시오.

풀이>
1) 냅색문제 확인
- 추를 조합해서, 확인할 구슬의 무게를 맞췄을때, 가능한 것인지?
- 추의 무개를 쪼갤수 없다.
- 30 * 40,000 <= 1억
- 추를 중복 선택할수 없다.
2) 특정수 만드려는 문제
3) 점화식 정의 및 설계
- dp[i][j] = i번째 까지 추를 고려했을때, 구슬의 무게 j를 만들수 있으면 1, 아니면 0

for (int i = 0; i <= N; i++) dp[i][0] = 1;
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= MAXK; j++) {
dp[i][j] = dp[i - 1][j]; // 추를 안올리는 경우
if (dp[i - 1][abs(j - S[i])] == 1) { // 추의 오른쪽에 두는 경우.
dp[i][j] = 1;
}
if (j + S[i] < MAXK && dp[i - 1][j + S[i]] == 1) { // 추의 왼쪽에 두는 경우
dp[i][j] = dp[i - 1][j + S[i]];
}
}
}

4) 물건중복X
5) DP 테이블 ( 예제 입력 2로 하자)
- 기저조건 있음.
4
2 3 3 3
3
1 4 10

   | 1 0 0 0 0 0 0 0 0 0 0
2 | 1 0 1 0 0 0 0 0 0 0 0
3 | 1 1 1 1 0 1 0 0 0 0 0
3 | 1 1 1 1 1 1 1 0 1 0 0
3 | 1 1 1 1 1 1 1 1 1 1 0