Consumer

題意：

n個(gè)游戲機(jī)，有w錢
每個(gè)游戲機(jī)上有游戲，每個(gè)游戲有價(jià)格和娛樂值，游戲機(jī)有價(jià)格，沒有娛樂值，玩游戲必須要用對(duì)應(yīng)的游戲機(jī)，問娛樂值最大是多少

題解：

有依賴關(guān)系的背包問題
對(duì)于一個(gè)游戲機(jī)，游戲機(jī)本身沒有娛樂值，但是上面的游戲有娛樂值，所以我們可以選擇不要這個(gè)游戲機(jī)，或者要游戲機(jī)以及里面的物品，我們要求出選擇這個(gè)箱子以及其中的物品在各個(gè)費(fèi)用下所能取的最大價(jià)值
dp[i][j]就表示前i個(gè)游戲機(jī)，花費(fèi)在j以內(nèi)的最大價(jià)值
如果j<游戲機(jī)價(jià)格,說明連游戲機(jī)都買不起，更別想游戲，所以dp[i][j]=-1;
如果j>游戲機(jī)價(jià)格val，j中val用于買游戲機(jī)，此時(shí)的狀態(tài)等于不選第i個(gè)游戲機(jī)，有j-val錢的狀態(tài)dp[i][j]=dp[i-1][j-val]

現(xiàn)在的dp[][]表示選了游戲機(jī)后的狀態(tài)，直接對(duì)游戲機(jī)中的游戲進(jìn)行01背包求各個(gè)費(fèi)用下的最大價(jià)值

if(dp[i][j-cost]!=-1)dp[i][j] = max(dp[i][j], dp[i][j - cost] + val);

經(jīng)過上述操作，我們得到了選擇當(dāng)前游戲機(jī)i 的的情況下，各個(gè)費(fèi)用下的最大價(jià)值
然后我們?nèi)ズ筒贿x這個(gè)游戲機(jī)的情況下，各個(gè)費(fèi)用下的最大價(jià)值取最大值，這樣就得到挑選過游戲機(jī)i后得到的各個(gè)費(fèi)用的最大值
不選游戲機(jī)就是dp[i-1][…]

代碼：

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> //#define LOCAL = 1; using namespace std; typedef long long ll; const int Max = 1e5 + 10;int n, m; ll dp[55][Max];int main() {while (scanf("%d%d", &n, &m) != EOF){memset(dp, 0, sizeof(dp)); //初始化for(int i = 1 ;i <= n;i ++){int box, num;scanf("%d%d", &box, &num);for (int j = 0;j < box; j++) //總費(fèi)用小于box，無法買任何物品dp[i][j] = -1;for (int j = box;j <= m; j++) //由前一個(gè)狀態(tài)j-box，選擇了當(dāng)前的游戲機(jī)后轉(zhuǎn)移而來dp[i][j] = dp[i - 1][j - box];//上述表示選擇了當(dāng)前的游戲機(jī)后的價(jià)值（沒有和不選進(jìn)行比較）for(int k = 0 ;k < num ; k ++) //由01背包從選擇了箱子的狀態(tài)轉(zhuǎn)移到其余狀態(tài){int cost;ll val;scanf("%d%lld", &cost, &val);for(int j = m ; j >= cost ;j --){if(dp[i][j-cost] != -1){dp[i][j] = max(dp[i][j], dp[i][j - cost] + val);}}}for (int j = 0;j <= m;j++) //和不選擇此盒子作比較dp[i][j] = max(dp[i][j], dp[i - 1][j]);}printf("%lld\n", dp[n][m]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Consumer的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。