意甲冠军：b(0 <= b <= 5)商品的种类，每个人都有一个标签c(1 <= c <= 999)，有需要购买若干k(1 <= k <=5)，有一个单价p(1 <= p <= 999)。有s(0 <= s <= 99)。问完毕採购最少须要多少钱。

题目链接：http://poj.org/problem?id=1170

——>>已有b种物品，再将每种优惠分别看成一种新物品，剩下就是全然背包问题了。。

设dp[i]表示购买状态为 i 时的最少花费（关于购买状态：00032表示第0种物品买2个，第1种物品买3个）。则状态转移方程为：

dp[i + product[j].nState] = min(dp[i + product[j].nState], dp[i] + product[j].nPrice)（j是枚举各种物品的物品下标）;

#include <cstdio>

#include <cstring>

#include <algorithm>

using std::min;

const int MAXN = 5 + 1;

const int MAXS = 6 * 6 * 6 * 6 * 6;

const int MAX_SIX = 6;

const int MAX_ID = 999 + 1;

const int MAX_OFFER = 99 + 1;

struct PRODUCT

{

    int nId;

    int nNum;

    int nPrice;

    int nState;

} product[MAXN + MAX_OFFER];

int nType;

int dp[MAXS];

int nTargetState;

int nSixPow[MAX_SIX];

int nId2Bit[MAX_ID];

void Init()

{

    nType = 0;

    nTargetState = 0;

}

void GetSixPow()

{

    nSixPow[0] = 1;

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

    {

        nSixPow[i] = nSixPow[i - 1] * 6;

    }

}

void CompletePack()

{

    memset(dp, 0x3f, sizeof(dp));

    dp[0] = 0;

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

    {

        for (int j = 0; j < nType; ++j)

        {

            if (i + product[j].nState > nTargetState) continue;

            dp[i + product[j].nState] = min(dp[i + product[j].nState], dp[i] + product[j].nPrice);

        }

    }

    printf("%d\n", dp[nTargetState]);

}

int main()

{

    int b, s, n;

    GetSixPow();

    while (scanf("%d", &b) == 1)

    {

        Init();

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

        {

            scanf("%d%d%d", &product[i].nId, &product[i].nNum, &product[i].nPrice);

            product[i].nState = nSixPow[i];

            nTargetState += nSixPow[i] * product[i].nNum;

            nId2Bit[product[i].nId] = i;

        }

        scanf("%d", &s);

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

        {

            int nId, nCnt;

            product[b + i].nState = 0;

            scanf("%d", &n);

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

            {

                scanf("%d%d", &nId, &nCnt);

                product[b + i].nState += nSixPow[nId2Bit[nId]] * nCnt;

            }

            scanf("%d", &product[b + i].nPrice);

        }

        nType = b + s;

        CompletePack();

    }

    return 0;

}