Dynamic Programing 4

DP 냅색 응용
• 숙달 되면 1차원 냅색으로 구현하자. (2차원 x)

• DP 아이템 줄이기 (물건 중복 안되는 경우)
○ 물건과 물건의 개수가 주어질 경우, 물건을 개수 만큼 추가하여 물건 리스트를 재정의하자!!!
§ Ex) (물건, count) {(2,3), (3,2)} ==> (2, 2, 2, 3, 3) ==> 5개의 물건.
○ 물건 * 물건 count가 클 경우 N * M >= 1억 이상 되는 경우
§ 물건 이진형태로 그룹핑 해서 물건리스트를 재구성 하자.
□ 모든 수는 2진수로 만들수 있음.
□ Ex) 물건, 무게 : 4, 아이템 개수 : 12 경우, 물건을 다 추가하게 되면 (4, 4, ….) 
® 만들수 있는 무게 (12개) : 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48
□ 2의 제곱수로 묶음.
® 1묶음, 2묶음, 4묶음, 5묶음 (8보다 작기때문) -> 4*1, 4*2, 4*4, 4*5 = 4, 8, 16, 20
□ 무게 : 5, 아이템 개수 : 8 경우, 물건을 다 추가하게 되면
® 만들수 있는 무게 (8개) : 5, 10, 15, 20, 25, 30, 35, 40
® 묶음? 1, 2, 4, 1 = 1 
□ 이 4개의 물건으로 기존 12개의 물건의 모든 조합의 무게 M을 만족시킬수 있다.
□ 코드

vector<int> items;
 int idx = 1;
  for(int i=0; i<N; i++) {
    cin >> val >> cnt;
        while (cnt > 0) {
  int t = min(cnt, idx); // 남은 묶음 만듬.
   items.push_back(val * t);
   cnt -= t;
   idx *= 2;
        }
    }

○ 그룹핑 할때 물건에 정의된 모든 항목들을 묶은 개수로 곱해준다.
§ 물건1 -> 가치2, 무게3 
§ 4묶음 한 경우,  재정의된 물건
□ 가치8, 무게 12 --> 물건 1


• 조건이 추가 될때
○ 조건에 해당할때 Dp 업데이트 수행.
§ 상자 적재 문제
□ 상자를 가로 회전 후 적재, 상자를 세로 회전 후 적재, 상자를 적재하지 않거나
§ 저울
□ 추를 왼쪽에 넣거나, 오른쪽에 넣거나, 올리지 않거나.

• Path Tracking
○ dp 테이블을 역추적 하면서 선택한 물건의 값 또는 인덱스를 구한다.
§ path 배열에 저장되는 값은 역추적 해서 구하려는 값 ( 물건의 값 또는 인덱스 )
○ Path 배열은 dp 배열 파라메터와 동일하게 가져감
§ int path[30][30];
§ int dp[30][30];
○ 초기 값
§ 마지막 index : N, 만들려는 최종 무게 : M
○ 인덱스가 0 일때까지, path[i][j] 값에서 선택한 물건의 무게를 빼주면서, 선택한 물건을 계속 역추적 한다.
§ i -= 1
§ j -= 물건의 무게
○ 예) 선택한 물건의 무게를 출력해라.
§ Path[i][j] = i 번째 물건 까지 고려했을때, j 무게를 만족할때, i 번째의 물건의 무게

int index = N;
int weight = M;
while (index > 0) {
auto w = path[index][weight];
ans.push_back(w); // 정답 갱신
weight -= w;
index--;
}

• dp 파라메터를 늘리는 경우(2차원 -> 3차원)
○ 상향식 경우.
§ 물건을 선택했을 때, 물건의 연관된 항목들을 쪼갤수 없는 경우.

○ 하양식 리커시브 경우
§ 더 좋은 결과값을 만들수 있는데, 점화식을 잘못 세워 탐색 못하는 경우.


1) 수강과목
https://www.acmicpc.net/problem/17845

N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)
공부 시간의 한계를 초과하지 않으면서 과목의 중요도 합이 최대가 되도록 몇 개만 선택하여 수강하기로 마음먹었다.
중요도가 최대가 되도록 과목을 선택했을 때, 최대가 되는 중요도를 출력하는 프로그램을 작성하시오.

1) 냅색문제 확인
- 과목을 조합해서, 공부 시간을 맞췄을때, 최대 중요도를 구하여라.
- 과목을 쪼갤수 없음.
- 1000 * 10,000 <= 1억….
○ 메모리 최적화 필요 2차원 --> 1차원
- 과목 중복 선택 X

2) 점화식 정의 및 설계
- Dp[i][j] = i번째 과목까지 고려, 공부시간이 j일때 최대 중요도 구하기.
- dp[j] = 공부시간이 j일때 최대 중요도 구하기.

cin >> N >> K;
// N /= 10; // debug
for (int i = 1; i <= K; i++) {
cin >> L[i] >> Time[i];
// Time[i] /= 10; // debug
}
for (int i = 1; i <= K; i++) {
for (int j = N; j >= Time[i]; j--) {
if (j - Time[i] >= 0) dp[j] = max(dp[j], dp[j - Time[i]] + L[i]);
}
}

3) DP 테이블
- 만들려는 공부시간 j를 10으로 나누어서 dp 테이블을 작성해보자
- N /= 10; // debug, Time[i] /= 10; // debug
- 0 0 0 0 650 650 700 700 710


2) 기업투자
https://www.acmicpc.net/problem/2662
투자 금액 N과 투자 가능한 기업들의 개수 M이 주어진다. (1 ≤ N ≤ 300, 1 ≤ M ≤ 20)

 

1) 냅색문제 확인
- 기업당 한번의 투자,
- 금액을 쪼갤수 없음.
- 기업당 투자금액 중복 선택 안됨.
- 현재 투자 금액을 구하기 위한 방식이, 기존 냅색과 다름.
○ 기존 냅색 방식은 index를 통해 현재 투자금액을 얻을 수 있지만,
○ 투자 금액을 전부 조사해야 함.
○ 복잡한 경우 냅색 2차원..

2) 점화식 정의 및 설계
- p[i][j] = i번째 기업 고려시, 총 j원 투자했을때, 이익금
- DP 배열
○ dp[i][j] = i번째 기업까지 고려했을때, 총 j 투자했을때 최대 이익금
○ path[i][j] = i번째 기업까지 고려했을때 총 j 투자했을때, 현재 투자 한 액수

3) PathTracking 적용
4) 코드.

for (int i = 1; i <= M; i++) { // i  번째 기업
for (int cost = 1; cost <= N; cost++) { // cost 총 투자 금액일때
for (int j = 0; j <= cost; j++) { // j원 투자했을때
if (dp[i][cost] < dp[i - 1][cost - j] + p[i][j]) {
dp[i][cost] = dp[i - 1][cost - j] + p[i][j];
path[i][cost] = j;
}
}
}
}
vector<int> l;
int curr = M;
int cost = N;
while (curr > 0) {
auto inveset = path[curr][cost];
l.push_back(inveset);
cost -= inveset;
curr--;
}

3) 동전 분배
https://www.acmicpc.net/problem/1943

 

1) 냅색문제 확인
- 동전을 조합해서, 원장이 준금액을 맞췄을때, 그 돈을 반으로 나눌수있는지 여부(1, 0)
- 동전을 쪼갤수 없음.
- 100 * 물건의 개수 * 100,000 <= 1억
○ 물건의 개수가 10개만 해도 시간초과
○ 이진수로 그룹핑 하자.
§ 이진수로 그룹핑 해도 물건의 개수는 최소 100개 이상
○ 메모리 최적화 진행
§ 100 * 100,000 = 10,000,000 == 10MB  <= 128MB (제한)
§ Dp 1차원으로 하자.
- 동전을 여러 개 사용 ? X 혼동하지말자.

2) 문제 분석
- Total / 2 금액을 만들수 있으면, 1, 아니면 0
- 애초에 M을 전체 금액 / 2 로 설정.

2) 점화식 정의 및 설계
- 2차원 : dp[i][j] = i번째 까지 동전 고려, j 금액을 만들수 있으면 1, 아니면 0
- 1차원 : dp[j] = j 금액을 만들수 있으면 1, 아니면 0
- 2차원 코드

○ int dp[901][100001]; // 첫번째 인덱스 크기가 애매함 : coins.size()
int total = 0;
for (int i = 0; i < N; i++) {
int coin, cnt;
cin >> coin >> cnt;
total += coin * cnt;
int idx = 1;
while (cnt > 0) {
int t = min(cnt, idx);
coins.push_back(coin * t);
cnt -= t;
idx *= 2;
}
}
if (total % 2 != 0) { printf("0\n"); continue; }
int M = total / 2;

for (int i = 0; i < coins.size(); i++) dp[i][0] = 1;
for (int i = 0; i < coins.size(); i++) {
for (int j = 0; j <= M; j++) {
dp[i + 1][j] = dp[i][j];
if (j - coins[i] >= 0 && dp[i][j - coins[i]] == 1) {
dp[i + 1][j] = 1;
}
}
}
printf("%d\n", dp[coins.size()][M]);

- 1차원 코드

dp[0] = 1;
for (int i = 0; i < coins.size(); i++) {
for (int j = M; j >= coins[i]; j--) {
if (j - coins[i] >= 0 && dp[j - coins[i]] == 1) {
dp[j] = 1;
}
}
}

3) DP 테이블
- Input 아래 에 대해서 해보자.
3
1 1
2 1
3 1
Ouput
1 0 0 0
1 1 0 0
1 1 1 1


4) 평범한 배낭 2
https://www.acmicpc.net/problem/12920

 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000), N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게
V는 물건의 무게, C는 물건을 가방에 넣었을 때 올라가는 민호의 만족도, K는 물건의 개수

집에 있는 모든 물건들을 가방에 넣으면 민호가 느낄 수 있는 만족도는 최대가 될 것이다. 
하지만 민호가 들 수 있는 가방의 무게는 정해져 있어 이를 초과해 물건을 넣을수가 없다.
민호가 만족도를 최대로 느낄 수 있는 경우를 찾아보자.
단, 집에 동일한 물건들이 여러개가 있을 수 있기 때문에 한 물건을 두개 이상 챙기는 것도 가능하다.

1) 냅색문제 확인
- 물건들을 조합해서, 가방의 최대무게를 맞췄을때, 최대의 만족도
- 물건은 쪼갤수 없음.
- 100 * 물건의 개수 * 10000 >= 1억
○ 이진수로 그룹핑 진행
○ 메모리 최적화 진행

2) 점화식 정의 및 설계
- dp[i][j] = 물건 i번째까지 고려했을때, j 가방에 무게를 맞췄을때 최대 만족도

- 2차원 코드

int N, M;
int dp[10001][10001]; // 100MB
for (int i = 0; i < N; i++) {
int v_, c_, k_;
cin >> v_ >> c_ >> k_;
int idx = 1;
while (k_ > 0) {
int t = min(k_, idx);
v.push_back(v_ * t);
c.push_back(c_ * t);
k_ -= idx;
idx *= 2;
}
}
for (int i = 0; i < v.size(); i++) {
for (int j = 0; j <= M; j++) {
dp[i + 1][j] = dp[i][j];
if (j - v[i] >= 0) {
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - v[i]] + (c[i]));
}
}
}
ans = dp[v.size()][M];
printf("%d\n", ans);

- 1차원 코드

○ int dp[10001];
for (int i = 1; i < v.size(); i++) {
for (int j = M; j >= v[i]; j--) {
dp[j] = max(dp[j], dp[j - v[i]] + (c[i]));
}
}
ans = dp[M];

- 2차원 DP 테이블
○ Input
2 3
2 7 1
1 9 3
○ output
0 0 0 0
0 0 7 7
0 9 9 16
0 9 18 27