題意: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; }