8.21日記
Table of Contents
Powered by Ghostface's Emacs
P.S.今天是挑戰(zhàn)30天沖擊省一的第11天，目前階段：TMD 動(dòng)態(tài)規(guī)劃之背包問題（我是真做夠了，每次做我都感覺自己跟弱智一樣）
歡迎收看今天的爆0&懵逼日志：
今日概述：
1.刷了幾個(gè)題
2.經(jīng)過我的一番折騰，又雙叒叕安裝了 Kali Linux
第一題：P1049 [NOIP 2001 普及組] 裝箱問題
題目描述
有一個(gè)箱子容量為 \(V\)，同時(shí)有 \(n\) 個(gè)物品，每個(gè)物品有一個(gè)體積。
現(xiàn)在從 \(n\) 個(gè)物品中，任取若干個(gè)裝入箱內(nèi)（也可以不取），使箱子的剩余空間最小。輸出這個(gè)最小值。
## 輸入格式
第一行共一個(gè)整數(shù) \(V\)，表示箱子容量。
第二行共一個(gè)整數(shù) \(n\)，表示物品總數(shù)。
接下來 \(n\) 行，每行有一個(gè)正整數(shù)，表示第 \(i\) 個(gè)物品的體積。
## 輸出格式
- 共一行一個(gè)整數(shù)，表示箱子最小剩余空間。
## 說明/提示
對(duì)于 \(100\%\) 數(shù)據(jù)，滿足 \(0<n \le 30\)，\(1 \le V \le 20000\)。
【題目來源】
NOIP 2001 普及組第四題
解題過程
21:44 start；
R 讓我們修改一下題目描述：給定N個(gè)物品和容量為V的背包，每個(gè)物品的價(jià)值與重量相等，求出最大價(jià)值與背包容量差的絕對(duì)值；
T 所以啊，兄弟們，這就是人機(jī)題；
T 開搞；
E 那么，最終一共用時(shí)7min，AC；
T 所以啊，水題好，水題能增加信心；
第二題：P1060 [NOIP 2006 普及組] 開心的金明
題目描述
金明今天很開心，家里購置的新房就要領(lǐng)鑰匙了，新房里有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對(duì)他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過 \(N\) 元錢就行”。今天一早金明就開始做預(yù)算，但是他想買的東西太多了，肯定會(huì)超過媽媽限定的 \(N\) 元。于是，他把每件物品規(guī)定了一個(gè)重要度，分為 \(5\) 等：用整數(shù) \(1-5\) 表示，第 \(5\) 等最重要。他還從因特網(wǎng)上查到了每件物品的價(jià)格（都是整數(shù)元）。他希望在不超過 \(N\) 元（可以等于 \(N\) 元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。
設(shè)第\(j\)件物品的價(jià)格為 \(v_j\)，重要度為 \(w_j\)，共選中了 \(k\) 件物品，編號(hào)依次為 \(j_1,j_2,…,j_k\)，則所求的總和為：
請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿足要求的購物單。
## 輸入格式
第一行，為 \(2\) 個(gè)正整數(shù)，用一個(gè)空格隔開：\(n,m\)（\(n<30000,m<25\)）其中 \(n\) 表示總錢數(shù)，\(m\) 為希望購買物品的個(gè)數(shù)。
從第 \(2\) 行到第 \(m+1\) 行，第 \(j\) 行給出了編號(hào)為 \(j-1\) 的物品的基本數(shù)據(jù)，每行有 \(2\) 個(gè)非負(fù)整數(shù) \(v,p\)（其中 \(v\) 表示該物品的價(jià)格 \((v \le 10000)\)，\(p\) 表示該物品的重要度（\(1\le p\le5\)）。
## 輸出格式
\(1\) 個(gè)正整數(shù)，為不超過總錢數(shù)的物品的價(jià)格與重要度乘積的總和的最大值（\(<100000000\)）。
NOIP 2006 普及組 第二題
解題過程：
21:57 start;
T 仍然是水題，我們修改題目描述：給定m個(gè)物品和容量為n的背包，其中每個(gè)物品的價(jià)值都是其重要度與重量的乘積，求出最大價(jià)值；
T P.S.這里不可以最后乘權(quán)值，因?yàn)檫@樣會(huì)導(dǎo)致局部最優(yōu)解；
T&P 我們開搞；
E 最終用時(shí)：9min，AC；
T 還是水題好做；
今日總結(jié)：
今天呢，受限于時(shí)間，沒做幾個(gè)題（2個(gè)），但是做得很高興（大概因?yàn)槎际撬}吧）；
然后，家里那 該死的 Wifi是真tm難用，動(dòng)不動(dòng)就丟包，害得我Kali差點(diǎn)沒用上；
滲透測試的學(xué)習(xí)每天也來一點(diǎn)點(diǎn)，雖然不是主線任務(wù)，但是學(xué)一下放松放松；
好了，先到這吧；
“眾所周知，研究珂學(xué)的最好方式是A了這道題”
“神槍手是拿子彈喂出來的”，所以，“神OIer是拿題目喂出來的”
Upt 2025.8.21 22:22
ghostface
浙公網(wǎng)安備 33010602011771號(hào)