程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj - 1170 - Shopping Offers(狀態壓縮dp)

poj - 1170 - Shopping Offers(狀態壓縮dp)

編輯:C++入門知識

poj - 1170 - Shopping Offers(狀態壓縮dp)


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


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved