7579 app
알고리즘(배낭정리, DP)
1
2
1. 배낭정리 응용. 최대 비용을 가방에 담을 수 있는 최대 무게로 보고, 메모리를 가치로 본다
2. 이렇게 2차원 배열을 완성하고, 필요한 메모리 이상이며 비용이 최소인 칸을 판별하고 출력하면 된다.
구현법
1
2
1. 최대 앱 개수는 100개이므로, 101행, 앱 당 최대 비용은 100 이므로 10001열을 선언하여 구현하면 됨.
2. 2차원 배열 완성하고나서는 첫번째 원소부터 검사하여, 메모리가 필요이상으로 있는데, 비용이 최소인 것을 찾으면 됨.
코드
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
#include <iostream>
#define MAX_N 100
#define MAX_MEMORY 10000000
using namespace std;
int numOfApp, a[MAX_N], c[MAX_N], m, maxValue;
int DP[105][10020];
int getMin();
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
cin >> numOfApp >> m;
for (int i = 0; i < numOfApp; i++)
cin >> a[i];
for (int i = 0; i < numOfApp; i++) {
cin >> c[i];
maxValue += c[i];
}
cout << getMin();
}
int getMin(){
for (int i = 1; i <= numOfApp; i++) {
for (int j = 1; j <= maxValue; j++) {
if (c[i-1] > j)
DP[i][j] = DP[i - 1][j];
else
DP[i][j] = max(a[i-1] + DP[i - 1][j - c[i-1]], DP[i - 1][j]);
}
}
int minValue = 2000000000;
for (int i = 0; i <= numOfApp; i++) {
for (int j = 0; j <= maxValue; j++) {
if (DP[i][j] >= m && minValue > j)
minValue = j;
}
}
return minValue;
}