跳至主要內容
Lizely

背包問題計算機

在整數容量限制內,找出不可分割項目的最高價值 0/1 組合。

隱私權:你的檔案不會離開裝置,所有處理均在瀏覽器本機完成。

使用方式

  1. 1.輸入 1 到 10,000 的整數容量。
  2. 2.每行新增一個不可分割項目:名稱、正整數重量與非負價值,以逗號分隔。
  3. 3.求解 0/1 模型,檢查選取項目與假設,必要時複製結果。

關於背包問題計算機

背包問題計算機會在單一容量內選出總價值最高的一組不可分割項目。輸入整數容量,以及每行「名稱, 重量, 價值」資料後,結果會列出選取項目、總價值、總重量與未使用容量,並可複製純文字結果。

此頁解的是經典的單容器 0/1 背包問題:每個項目只能不選或選一次,不能切割、重複選取或部分裝入。實作使用整數容量的動態規劃;對每個項目與每個可用容量,比較「不選」與「選取後加上先前最佳可行值」,最後再回溯出選取的項目。相同價值時會保留較早的解,因此相同輸入會得到可重現結果。

「精確」只針對這個有界模型:一個容量、正整數重量、非負價值、每項至多一次。它不處理尺寸、平衡、易碎性、項目相依、不可相容組合、期限、風險或不確定性;數學最佳的單一價值組合不一定適合真實世界。容量最高 10,000、項目最多 100 個,以控制瀏覽器記憶體與回應時間。

方法與來源

先驗證一個整數容量與最多 100 個具唯一名稱的項目,再建立標準 0/1 動態規劃表。每個項目與容量都比較不選取和選取兩種值;同值時保留不選取以維持決策可重現,最後回溯最大價值的選取組合,並確認每個項目最多出現一次且總重量不超過容量。

常見問題

結果一定是最佳解嗎?
對輸入的有界 0/1 模型是:一個容量、整數重量、非負價值且每個項目只能選一次。
可以把一個項目拆開或多選一次嗎?
不可以。每行都代表一個不可分割項目,只能選取零次或一次。
為什麼重量必須是整數?
動態規劃表為每個容量單位建立一個狀態。若原始重量有固定小數,可先一致地縮放後輸入。
它會處理實際包裝箱嗎?
不會。它只處理一個標量重量或成本,沒有模擬尺寸、平衡、脆弱度或其他實體限制。

計算工具 使用指南

查看全部