题意：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 
  
   
#include 
   
     #include 
    
      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; }