先上題

描述

終于到了開(kāi)開(kāi)心心的暑假，然而對(duì)于一名ACMer來(lái)說(shuō)，暑假并沒(méi)有那么輕松。fudq跟我說(shuō)：“我們ACMer修的，是一份境界。外修語(yǔ)法，內(nèi)修算法。以數(shù)據(jù)為根，算天算地算自己。我這有幾本書(shū)，你暫且拿去研修”。然后他給了我一本《算法入門(mén)經(jīng)典》，一本《算法導(dǎo)論》，一本《算法藝術(shù)與信息學(xué)競(jìng)賽》balabalabala....等等等等，我記得他當(dāng)時(shí)是用卡車(chē)拖過(guò)來(lái)的。不過(guò)在感激得痛哭流涕的同時(shí)，C.yi發(fā)現(xiàn)了一個(gè)嚴(yán)重的問(wèn)題??那就是怎么把這些書(shū)都帶回去呢？要知道行李都是有限重的，而且苦逼的C.yi回家只能背一個(gè)書(shū)包。看著愁眉苦臉痛哭流涕的C.yi，學(xué)長(zhǎng)鄒神跳了出來(lái)。他說(shuō)“看你這一臉苦逼的，莫非是在愁傅總給你的書(shū)你怎么帶回去？哈哈，不要問(wèn)我怎么知道，那什么外修語(yǔ)法內(nèi)修算法什么鬼的他當(dāng)年也跟我說(shuō)過(guò)，我可以告訴你一個(gè)好辦法。你可以根據(jù)書(shū)的難度和重要程度以及是否適合你現(xiàn)在學(xué)習(xí)給書(shū)評(píng)定一個(gè)價(jià)值，然后有選擇的帶”。這可又愁剎了C.yi，怎么在書(shū)包的限重之下盡可能價(jià)值高的把書(shū)帶回家呢？請(qǐng)你幫他寫(xiě)一個(gè)代碼來(lái)解決這個(gè)問(wèn)題。

輸入

第一行是一個(gè)數(shù)字T,表示有T組數(shù)據(jù)。
對(duì)于每一組數(shù)據(jù)，首先輸入的是書(shū)的本書(shū)n(n<=1000)，和書(shū)包的限重w（w<=1000）。
再然后有n個(gè)整數(shù)表示書(shū)的價(jià)值。
再再然后有n個(gè)整數(shù)表示每本書(shū)的重量。

輸出

每組數(shù)據(jù)輸出符合要求的最大價(jià)值。(結(jié)果不會(huì)超過(guò)int范圍)

樣例輸入1? 1 5 10 1 2 3 4 5 5 4 3 2 1 樣例輸出1 14

#include<iostream> #include<algorithm> #include<string.h> using namespace std;int B[1010]; int value[1010], weight[1010]; int main() {int T;scanf("%d", &T);while (T--){memset(B, 0, sizeof(B));int n, w;scanf("%d%d", &n, &w);for (int i = 1; i <= n; i++){scanf("%d", &value[i]);}for (int i = 1; i <= n; i++){scanf("%d", &weight[i]);}for (int i = 1; i <= n; i++){for (int j = w; j >= weight[i]; j--){B[j] = max(B[j], B[j - weight[i]] + value[i]);}}cout << B[w] << endl;}return 0; }
不懂為什么B數(shù)組不能在定義時(shí) B【1010】={0}，會(huì)wa

只能用memset

總結(jié)

以上是生活随笔為你收集整理的BFU C.yi的书包 01背包【水题】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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