7579 app
์๊ณ ๋ฆฌ์ฆ(๋ฐฐ๋ญ์ ๋ฆฌ, DP)
1. ๋ฐฐ๋ญ์ ๋ฆฌ ์์ฉ. ์ต๋ ๋น์ฉ์ ๊ฐ๋ฐฉ์ ๋ด์ ์ ์๋ ์ต๋ ๋ฌด๊ฒ๋ก ๋ณด๊ณ , ๋ฉ๋ชจ๋ฆฌ๋ฅผ ๊ฐ์น๋ก ๋ณธ๋ค
2. ์ด๋ ๊ฒ 2์ฐจ์ ๋ฐฐ์ด์ ์์ฑํ๊ณ , ํ์ํ ๋ฉ๋ชจ๋ฆฌ ์ด์์ด๋ฉฐ ๋น์ฉ์ด ์ต์์ธ ์นธ์ ํ๋ณํ๊ณ ์ถ๋ ฅํ๋ฉด ๋๋ค.
๊ตฌํ๋ฒ
1. ์ต๋ ์ฑ ๊ฐ์๋ 100๊ฐ์ด๋ฏ๋ก, 101ํ, ์ฑ ๋น ์ต๋ ๋น์ฉ์ 100 ์ด๋ฏ๋ก 10001์ด์ ์ ์ธํ์ฌ ๊ตฌํํ๋ฉด ๋จ.
2. 2์ฐจ์ ๋ฐฐ์ด ์์ฑํ๊ณ ๋์๋ ์ฒซ๋ฒ์งธ ์์๋ถํฐ ๊ฒ์ฌํ์ฌ, ๋ฉ๋ชจ๋ฆฌ๊ฐ ํ์์ด์์ผ๋ก ์๋๋ฐ, ๋น์ฉ์ด ์ต์์ธ ๊ฒ์ ์ฐพ์ผ๋ฉด ๋จ.
์ฝ๋
#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;
}