一、問題描述

設給定N項物品， 大小為s1, s2, s3, …, sn, 每個物品的都不超過1； 現有大小為1的箱子若干個， 將物品裝入箱子中， 盡量使用少的箱子裝滿所有物品；
實例：
現有一列物品：0.2， 0.5， 0.4， 0.7， 0.1， 0.3， 0.8；其中一種裝箱方案如下所示：

裝箱問題是一個NP完全問題， NP完全問題的最優解的時間復雜度不能是一個二項式的（通常NP問題的時間復雜度是指數型的）；因此， 當獲知這是一個NP完全問題， 就要考慮不糾結于求解其最優解，通常求解器近似解，并且近似解的時間復雜度很小；

二、區分聯機算法與脫機算法

1） 聯機算法
聯機算法相當于輸入數據不是一次性傳遞到算法的，每來一個數據， 算法就要處理這個數據；算法對已經處理過的數據并不能修改， 算法對未來的數據也無法預測；

2） 脫機算法
脫機算法的輸入數據通常是一組事先已知的數據， 算法可以對數據進行預先處理，例如排序。之后在進行裝箱算法。一般脫機算法能夠得到更優的解；

三、近似裝箱問題的求解算法

1） 下項適配(next fit)
當處理一個物品的時候， 檢查當前箱子容量是否足夠；如果足夠， 就將物品放入當前箱子， 如果不足， 就重新開辟一個新的箱子；
下項適配的代碼如下：

#include <stdio.h> #include <stdlib.h>#define N 7 float item[] = { 0.2, 0.5, 0.4, 0.7, 0.1, 0.3, 0.8 }; float box[N] = { 1, 1, 1, 1, 1, 1, 1 }; int flags[N] = { 0 };void binningNextFit() {int index = 0;for (int i = 0; i < N; i++) {if (item[i] <= box[index]) {box[index] -= item[i];flags[i] = index + 1; }else {index++;box[index] -= item[i];flags[i] = index + 1;}} }int main() {binningNextFit();for (int i = 0; i < N; i++) printf("box[%d]: %5.2f, flags:%d\n", i, box[i], flags[i]);return 0; }

下項適配的結果是：

2） 首次適配(first fit)
每次考慮將一個物品放入箱子中的時候，都從第一個箱子開始嘗試放入物品；當所有的已打開的箱子的容量都不滿足的時候， 重新開辟一個新的箱子；
首次適配的代碼如下:

#include <stdio.h> #include <stdlib.h>#define N 7 float item[] = { 0.2, 0.5, 0.4, 0.7, 0.1, 0.3, 0.8 }; float box[N] = { 1, 1, 1, 1, 1, 1, 1 }; int flags[N] = { 0 };void binningFirst() {int index = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (box[j] >= item[i]) {box[j] -= item[i];flags[i] = j + 1;break;}}} }int main() {binningFirst();for (int i = 0; i < N; i++) printf("box[%d]: %5.2f, flags:%d\n", i, box[i], flags[i]);return 0; }

首次適配的情況如下:

3） 最佳適配(best fit)
每次考慮將一個物品放入箱子的時候， 都考慮所有能夠容納物品的箱子中， 選取剩余容量最小的那個箱子；
最佳適配算法的代碼如下:

#include <stdio.h> #include <stdlib.h>#define N 7 float item[] = { 0.2, 0.5, 0.4, 0.7, 0.1, 0.3, 0.8 }; float box[N] = { 1, 1, 1, 1, 1, 1, 1 }; int flags[N] = { 0 };//數據的類型要設置對， 索引設置為int， 數據類型設置為float void binningFirst() {for (int i = 0; i < 6; i++) {float min = 1;int index = 0;for (int j = 0; j < N; j++) {float tmp = box[j] - item[i];if (tmp >= 0 && tmp < min) {min = tmp;index = j;}}box[index] -= item[i];flags[i] = index + 1;} }int main() {binningFirst();for (int i = 0; i < N; i++) printf("box[%d]: %5.2f, flags:%d\n", i, box[i], flags[i]);return 0; }

最佳適配的裝箱情況如下:

四、裝箱問題分析

采用下項適配， 需要5個箱子；
采用首次適配和最佳適配， 需要4個箱子；
而實際上最優解只需要3個箱子；
中上所述， 使用上述三個算法求得的裝箱問題只能得出近似最優解；

總結

以上是生活随笔為你收集整理的近似装箱问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。