#include <stdio.h>
__inline int max(int a, int b) {
return a > b ? a : b;
}
struct data {
char name[21];
int weight;
int need;
};
int C, N, W;
struct data good[101];
int Cache[1001][101];
int dp(int wei, int order) {
int *ret = &Cache[wei][order];
if (*ret != -1) return *ret;
*ret = 0;
for (int i = order+1; i <= N; i++)
{
if (wei >= good[i].weight) {
*ret = max(*ret, good[i].need + dp(wei - good[i].weight, i));
}
}
return *ret;
}
int Answer[101];
int ord;
void find_ans(int Ans, int wei, int order) {
for (int i = order+1; i <= N; i++)
{
if (Ans == good[i].need + Cache[wei - good[i].weight][i]) {
Answer[ord] = i;
ord++;
find_ans(Ans-good[i].need, wei - good[i].weight, i);
break;
}
}
}
int main() {
scanf("%d", &C);
for (int i = 0; i < C; i++)
{
scanf("%d %d", &N, &W);
for (int i = 0; i <= N; i++)
{
for (int j = 1; j <= W; j++)
{
Cache[j][i] = -1;
}
}
for (int j = 1; j <= N; j++) scanf("%s %d %d", &good[j].name, &good[j].weight, &good[j].need);
ord = 0;
find_ans(dp(W, 0), W, 0);
printf("%d %d\n", dp(W, 0),ord);
for (int i = 0; i < ord; i++)
{
printf("%s\n", good[Answer[i]].name);
}
}
}
previc
[[problem:PACKING]] 문제 풀이입니다.
샘플케이스 돌렸을땐 문제없이 도는데, 답안제출하면 제목같은 에러가 발생하네요..
어디가 문제인지 알려주실분 계신가요?
10년 전