跳至主要內容
Lizely

裝箱問題計算機

用可重現的 FFD 放置法，把附標籤的項目大小分配到等容量箱子，並查看使用率與大小下界。

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

使用方式

  1. 1.輸入每個箱子的正容量。
  2. 2.每行輸入一個項目，格式為「標籤, 大小」或只輸入大小；最多可輸入 1,000 個。
  3. 3.執行 FFD，查看每箱項目、使用率、剩餘容量與下界，必要時複製方案。

關於裝箱問題計算機

裝箱問題計算機會把帶有標籤與大小的項目放入相同容量的箱子。輸入每箱容量及每行一個項目後，它會用 First Fit Decreasing（FFD）產生確定性的裝箱方案、每箱使用量、剩餘量、使用率與依總大小得出的下界。FFD 會先把項目依大小由大到小排序，再把每個項目放入第一個仍裝得下的箱子；相同大小的項目維持原始輸入順序，因此同一份輸入會得到可重現的結果。FFD 是快速實用的啟發式方法，但不保證使用全域最少的箱數；畫面上的下界也不是最優性的證明。

方法與來源

工具先驗證 1 至 1,000 個項目與每箱正容量，依大小遞減並以原始順序作為同大小的穩定排序，然後將每個項目放進第一個剩餘容量足夠的箱子。輸出包含每箱項目、使用量、剩餘量、使用率與以總大小除以容量並向上取整的下界；下界不是最優性證明。

常見問題

FFD 是什麼？
First Fit Decreasing 會先由大到小排序項目，再將每個項目放入第一個容納得下的箱子；同一輸入會得到相同結果。
下界代表什麼？
下界是把所有項目大小相加後除以每箱容量並向上取整。任何有效方案至少需要這麼多箱子，但 FFD 使用的箱數可能較多。
為什麼某個項目被拒絕？
每個項目必須有非空白、最多 60 個字元的標籤，大小必須大於零且不大於箱子容量。每行只能使用「大小」或「標籤, 大小」格式。
這一定是最少箱數嗎？
不一定。FFD 是確定性啟發式方法，著重快速且可重現的方案；若必須證明最少箱數，需使用最佳化求解器。

相關工具

計算工具 使用指南

查看全部