[Algospot 저장용] PACKING

문제 출처 : https://algospot.com/judge/problem/read/PACKING

 

 

#include<stdio.h>
 
struct product {
    char name[21];
    int w;
    int imp;
};
 
struct queue {
    char* data[101];
    int front, rear;
    void init() { front = rear = 0; }
    void push(char inp[]) { data[front++] = inp; }
    char* pop() { return data[rear++]; }
    bool empty() { return front == rear; }
    int size() { return front - rear; }
}q;
 
product p[100];
int t, n, w, arr[1001][100];
 
int solve(int wei, int item)
{
    if (item == n || wei<0)return 0;
    int &ret = arr[wei][item];
    if (ret != 0)return ret;
 
    ret = solve(wei, item + 1);
 
    if (wei >= p[item].w)
    {
        int tmp = solve(wei - p[item].w, item + 1) + p[item].imp;
        ret = tmp > ret ? tmp : ret;
    }
    return ret;
}
 
void result(int wei, int item)
{
    if (item == n)return;
 
    if (arr[wei][item + 1] == arr[wei][item])result(wei, item + 1);
    else
    {
        q.push(p[item].name);
        result(wei - p[item].w, item + 1);
    }
}
 
int main()
{
    scanf("%d", &t);
 
    while (t--)
    {
        q.init();
        scanf("%d %d\n", &n, &w);
        for (int i = 0; i <= w; i++)for (int j = 0; j < n; j++)arr[i][j] = 0;
        for (int i = 0; i < n; i++)scanf("%s %d %d\n", p[i].name, &p[i].w, &p[i].imp);
        int ret = solve(w, 0);
        result(w, 0);
        printf("%d %d\n", ret, q.size());
        while (!q.empty())printf("%s\n", q.pop());
    }
}