(VS 라이센스가 만료되어 웹 C++에서 개발함 ㅠㅠ www.onlinegdb.com/online_c++_compiler)
0. Knapsack
도둑이 가방의 용량제한 안에서 최대한 가치를 갖도록 물건을 조합해서 넣는 문제이다.
어려울 것 없이 '1. 훔친다(goto next)+현재Value' 와 '2.안훔친다(goto next)' 두 step으로 계속해서 재귀문을 돌리면 된다.
1. 일반코드.
Knapsack은 sub fcn에서 '훔치냐' '안훔치냐' 두 개의 재귀를 호출하고, 그 중 큰 값을 return하면 된다.
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
33
34
35
36
37
38
39
|
#include <iostream>
using namespace std;
#define MAX(a,b) ((a)>(b)?(a):(b))
#define WEIGHT 0
#define VALUE 1
#define N 5
int items[N][2] = {
{10, 1},
{1, 1},
{5, 3},
{4, 2},
{8, 1},
};
int knapsack(int n, int cap) {
if(n==N)
return 0; // 마지막은 선택한게 없으므로 0값
int ret =0;
if(items[n][WEIGHT] <= cap) // 용량이 가능하다면
ret = knapsack(n+1, cap - items[n][WEIGHT]) + items[n][VALUE];
// 훔쳤을때. 훔친sub fcn결과와 현재 훔친물건 value 더함
int ret2 = knapsack(n+1, cap); // 안훔쳐
return MAX(ret, ret2); // 현재 시점에서 훔/안훔 중 큰 놈으로 ret
}
int main()
{
cout<<"Hello World";
//for(int i =0; i < 3; i++)
int rst = knapsack(0, 100);
cout<<rst;
return 0;
}
|
cs |
2. DP 추가
단순하게 N번 ITEM이 특정 CAPACITANCE 의 상황일 때 Value를 연산한 기록 있다면 해당 값을 바로 return한다.
아래의 코드와 같이 DP배열을 하나 추가해서 사용하자.(초기화값은 -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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
#include <iostream>
using namespace std;
#define MAX(a,b) ((a)>(b)?(a):(b))
#define WEIGHT 0
#define VALUE 1
#define N 5
int items[N][2] = {
{10, 1},
{1, 1},
{5, 3},
{4, 2},
{8, 1},
};
#define MAX_CAP 1000 // capacity max에 맞도록 dp배열 생성하기 위함
int dp[N][MAX_CAP]; // dp용 배열(N번 item이 CAP일때 이미 계산기록이 있으면
// 그대로 활용함)
int knapsack(int n, int cap) {
if(n==N)
return 0; // 마지막은 선택한게 없으므로 0값
//int ret =0; // dp없을때
/*******************************************/
int ret = dp[n][cap]; // **** dp배열에 n이 cap일때 미리 계산된 값 있음?
if(ret != -1) return ret; // **** dp값 return
/*******************************************/
if(items[n][WEIGHT] <= cap) // 용량이 가능하다면
ret = knapsack(n+1, cap - items[n][WEIGHT]) + items[n][VALUE];
// 훔쳤을때. 훔친sub fcn결과와 현재 훔친물건 value 더함
int ret2 = knapsack(n+1, cap); // 안훔쳐
ret = MAX(ret, ret2);// 현재 시점에서 훔/안훔 중 큰 놈으로 ret
/*******************************************/
dp[n][cap] = ret; // **** dp에 value write
/*******************************************/
return ret;
}
int main()
{
/*******************************************/
// dp init
for(int i = 0; i < N; i++)
for(int j = 0; j < MAX_CAP; j++)
dp[i][j] = -1;
/*******************************************/
int rst = knapsack(0, 100);
cout<<rst;
return 0;
}
|
cs |
'소프트웨어 > Algorithm' 카테고리의 다른 글
[Algo] Trie 간단 insert, find code (0) | 2021.04.06 |
---|---|
Math] Spline Interpolation (0) | 2019.01.02 |
Dijkstra (0) | 2015.09.20 |
gtk study 예정사항들 (0) | 2015.09.20 |
week3] dijkstra(heap sort, priority queue) (0) | 2015.09.20 |
week2] sort, tree, heap, graph 자료구조 마무리 (0) | 2015.09.20 |
Heap Sort (0) | 2015.09.14 |