2662 기업투자 https://www.acmicpc.net/problem/2662
알고스팟 PACKING https://algospot.com/judge/problem/read/PACKING
조합 최적화 문제로 유명한 Knapsack Ploblem(배낭문제)이다.
W의 무게를 담을 수 있는 가방이 있을 때 가방에 담을 수 있는 가장 높은 가치들의 합을 구하는것과 같은문제이다.
점화식은 보통 다음과 같다.
$DP[capacity][idx]$ = $max(DP[capacity][idx+1], DP[capacity - item[idx]][idx + 1])$
1. 1535 안녕
전형적인 Knapsack 문제이다.
#include <cstdio>
#include <cstring>
#include <algorithm>
int N;
int dhealth[21], gjoin[21];
int dp[101][21];
int solve(int h, int here){
if (here == N) return 0;
int &ret = dp[h][here];
if (ret != -1) return ret;
//here에서 인사를 안함
ret = solve(h, here + 1);
//here에서 인사를 함
if (h - dhealth[here] > 0)
ret = std::max(ret, solve(h - dhealth[here], here + 1) + gjoin[here]);
return ret;
}
int main(){
memset(dp, -1, sizeof(dp));
scanf("%d", &N);
for (int n = 0; n < N; n++)
scanf("%d", &dhealth[n]);
for (int n = 0; n < N; n++)
scanf("%d", &gjoin[n]);
printf("%d\n",solve(100, 0));
return 0;
}
| cs |
2. 2662 기업투자
$N$금액만큼 각 기업에 투자했을 때 최대 이득을 구하라고 한다. 뿐만아니라 어떻게 투자해야되는지도 구하란다.
마찬가지로 $money$(투자금액)를 $capacity$로 기업번호를 $idx$로 놓고 풀면된다.
어떻게 투자하는지는 다음문제에서 설명한다.
#include <cstdio>
#include <algorithm>
#include <cstring>
int N, M;
int dp[1111][21];
int cost[21] = { 0 } , gain[1111][21] = { 0 };
int ans[21];
int solve(int money, int here){
if (money == 0 || here == 0) return 0;
int &ret = dp[money][here];
if (ret != -1) return ret;
for (int t = 0; t <= money;t++)
ret = std::max(ret, solve(money - t, here - 1) + gain[t][here]);
return ret;
}
void reconstruct(int money, int here){
if (here == 0) return;
//here기업에 투자 안한 경우
if (solve(money, here) == solve(money, here - 1))
reconstruct(money, here - 1);
else{
int query_comp, query_money;
for (int t = 0; t <= money; t++){
if (solve(money, here) == solve(money - t, here - 1) + gain[t][here]){
ans[here] = t;
reconstruct(money - t, here - 1);
break;
}
}
}
}
int main(){
memset(dp, -1, sizeof(dp));
scanf("%d%d", &N, &M);
for (int n = 1; n <= N; n++){
int a;
scanf("%d", &a);
for (int m = 1; m <= M; m++){
scanf("%d", &gain[a][m]);
}
}
printf("%d\n",solve(N, M));
reconstruct(N, M);
for (int m = 1; m <= M; m++)
printf("%d ", ans[m]);
printf("\n");
return 0;
}
| cs |
3. PACKING (종만북 참고)
위와 유사한 문제이다.
이문제에서는 최대 절박도와 어떤 물건을 선택해야되는지를 구하는것인데
만약 $capacity$를 변화시키지 않고 $idx$만 변화시켰다면 해당 물건을 선택하지 않았다는 것이다.
반대로 $capacity$를 변화시켰다면 해당 물건을 선택한 것이다.
위의 문제에서도 $money$가 변화하지 않았다면 해당 기업에 투자하지 않은것이고
아니라면 회사가 여러개있으니 반복문을 돌려주며 미리 구했던 값과 일치하는 지점으로 계속
들어가면 투자기업과 금액을 알 수 있다.
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int N, M;
int w[101], c[101];
int dp[1001][101];
vector<int> ans2;
int solve(int cap, int item){
if (item == N + 1) return 0;
int &ret = dp[cap][item];
if (ret != -1) return ret;
ret = solve(cap, item + 1);
if (cap - w[item] >= 0)
ret = max(ret, solve(cap - w[item], item + 1) + c[item]);
return ret;
}
void reconstruct(int cap, int item){
if (item == N + 1) return;
if (solve(cap, item) == solve(cap, item + 1))
reconstruct(cap, item + 1);
else{
ans2.push_back(item);
reconstruct(cap - w[item], item + 1);
}
}
int main(){
int T;
scanf("%d", &T);
while (T--){
char str[101][25];
ans2.clear();
memset(dp, -1, sizeof(dp));
scanf("%d%d", &N, &M);
for (int n = 1; n <= N; n++)
scanf("%s%d%d", str[n], &w[n], &c[n]);
int ans1 = solve(M, 1);
reconstruct(M, 1);
printf("%d %d\n", ans1, ans2.size());
for (auto i : ans2)
printf("%s\n", str[i]);
}
return 0;
}
| cs |
댓글 없음:
댓글 쓰기