0 1背包問題（關(guān)于0 1背包問題的簡介）

2022-08-29 20:39:34 編輯：楊亨威來源：

導讀大家好，0 1背包問題，關(guān)于0 1背包問題的簡介很多人還不知道，現(xiàn)在讓我們一起來看看吧！1、背包問題(Knapsack problem)是一種組合優(yōu)化的...

大家好，0 1背包問題，關(guān)于0 1背包問題的簡介很多人還不知道，現(xiàn)在讓我們一起來看看吧！

1、背包問題(Knapsack problem)是一種組合優(yōu)化的NP完全問題。

2、問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價格最高。

3、問題的名稱來源于如何選擇最合適的物品放置于給定背包中。

4、相似問題經(jīng)常出現(xiàn)在商業(yè)、組合數(shù)學，計算復雜性理論、密碼學和應用數(shù)學等領(lǐng)域中。

5、也可以將背包問題描述為決定性問題，即在總重量不超過W的前提下，總價值是否能達到V？它是在1978年由Merkle和Hellman提出的。

6、背包問題已經(jīng)研究了一個多世紀，早期的作品可追溯到1897年??數(shù)學家托比亞斯·丹齊格（Tobias Dantzig，1884-1956）的早期作品，并指的是包裝你最有價值或有用的物品而不會超載你的行李的常見問題。

本文關(guān)于0 1背包問題的簡介就講解完畢，希望對大家有所幫助。

標簽：

免責聲明：本文由用戶上傳，如有侵權(quán)請聯(lián)系刪除！

本站除標明“本站原創(chuàng)”外所有信息均轉(zhuǎn)載自互聯(lián)網(wǎng) 版權(quán)歸原作者所有。