HDOJ 3033 I love sneakers!(패키지 그룹화)

제목:
어떤 사람이 신발을 사려고 하는데 k개의 브랜드가 있고 모든 브랜드는 j개의 모델이 있다. 모든 브랜드는 가격과 가치가 있기 때문에 이미 M위안 안에 모든 브랜드가 적어도 신발 한 켤레를 사는 최대 가치와 가치를 요구한다.
아이디어:
1. 각 그룹 중 최소한 한 명이 선택되어 이전의 최대 한 명과 약간의 차이가 있어야 하며, 문제를 다시 세분화해야 한다.
2. dp[i][j]는 i개 브랜드를 선정하고 비용을 j의 최대 가치로 하고 dp[i][j]는 정수로 상태가 존재하고 음수로 상태가 존재하지 않는다는 것을 나타낸다.
3. dp[i][j] = max(dp[i][j], dp[i][j - vk] + wk); i류 브랜드는 선택할 수 있고 k번째 아이템을 선택해야 한다.(첫 번째 k개 아이템을 선택하지 않는 것은 동일하기 때문에 전이 방정식을 생략)
   dp[i][j] = max(dp[i][j], dp[i - 1][j - vk] + wk); i류 브랜드 앞에서 선택하지 않았고 k번째 아이템을 선택해야 합니다.
4. 상태가 0에서 i이고 dp[0][j]=0이므로 나머지는 -INFS입니다.그래서 첫 번째 브랜드의 상태가 존재할 때만 두 번째 브랜드의 존재 상태를 유도하고 이런 식으로 추측할 수 있다.
5. 제목에는 2개의 함정이 있다. 첫째, 어떤 브랜드의 수량이 0인 경우도 있고 비용이나 가격이 0인 경우도 있기 때문에 상태 이동 방정식은 바꿀 수 없다.
 

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;



const int MAXD = 10010;

const int MAXN = 12;

const int INFS = 0x3fffffff;



vector<pair<int, int> > brand[MAXN];

int dp[MAXN][MAXD];



int main()

{

    int n, m, k;

    while (scanf("%d %d %d", &n, &m, &k) != EOF)

    {

        for (int i = 1; i <= k; ++i)

            brand[i].clear();



        for (int i = 0; i < n; ++i)

        {

            int id, w, v;

            scanf("%d %d %d", &id, &w, &v);

            brand[id].push_back(make_pair(w, v));

        }



        memset(dp[0], 0, sizeof(dp[0]));



        int cflag = 0;

        for (int i = 1; i <= k; ++i)

        {

            for (int v = 0; v <= m; ++v)

                dp[i][v] = -INFS;



            if (!brand[i].empty())

                ++cflag;



            for (int j = 0; j < brand[i].size(); ++j)

            {

                int w = brand[i][j].first;

                int val = brand[i][j].second;

                for (int v = m; v >= w; --v)

                {

                    dp[i][v] = max(dp[i][v], dp[i][v - w] + val);

                    dp[i][v] = max(dp[i][v], dp[i - 1][v - w] + val);

                }

            }

        }

        if (cflag == k && dp[k][m] > 0)

            printf("%d
", dp[k][m]);

        else

            printf("Impossible
");

    }

    return 0;

}