一维装箱问题

2023-10-29 13:39:04

Bin Packing Problem

一、问题描述

二、算法介绍及实现

注：（1）以下的文字表达中，桶 == 箱子，空间 == 容量；
（2）每个算法对应的程序默认读取所有测试文件并计算结果与耗时；

(一) 直接法
按照给定物品的顺序，判断当前桶能否装下当前物品，如果不能，则新开一个桶并将物品放入该桶中，接着便从该桶开始判断能否装下下一个物品（不再回头看前面的桶）。
这个算法是最简单也是最快的方法，但基本上对问题没有什么优化，效果不佳。

时间复杂度：O（n）
代码实现：

//算法一   
#include<stdio.h>  
#include<vector>  
#include<ctime>  
using namespace std;  
const char path[17][30] = {"Data/Waescher_TEST0005.txt", "Data/Waescher_TEST0014.txt", "Data/Waescher_TEST0022.txt", "Data/Waescher_TEST0030.txt", "Data/Waescher_TEST0044.txt", "Data/Waescher_TEST0049.txt", "Data/Waescher_TEST0054.txt", "Data/Waescher_TEST0055A.txt", "Data/Waescher_TEST0055B.txt", "Data/Waescher_TEST0058.txt", "Data/Waescher_TEST0065.txt", "Data/Waescher_TEST0068.txt", "Data/Waescher_TEST0075.txt", "Data/Waescher_TEST0082.txt", "Data/Waescher_TEST0084.txt", "Data/Waescher_TEST0095.txt","Data/Waescher_TEST0097.txt"} ;   
int main() {  
    for (int t = 0; t < 17; ++t) {  
        clock_t start, end;  
        start = clock();  
        FILE* file = fopen(path[t], "r");  
        int numItems, capacity;  
        fscanf(file, "%d%d", &numItems, &capacity);  
        vector<int> items(numItems);  
        int numBuckets = 1, remain = capacity;  
        for (int i = 0; i < numItems; ++i) {  
            fscanf(file, "%d", &items[i]);  
            if (remain > items[i]) remain -= items[i];  
            else {  
                numBuckets++;  
                remain = capacity - items[i];  
            }  
        }  
        end = clock();  
        printf("test file: %s, used %d bucket, running time: %lf seconds\n", path[t], numBuckets, ((double)end - start) / CLK_TCK);  
    }  
}

(二) First Fit
按照给出物品的顺序，维护一个桶的数组（用vector实现），每次从列表头开始依次向后遍历每一个桶，直到找到一个可以存放当前物品的桶，如果所有桶都不能满足，则新开一个桶并加到列表中去，并将当前物品放在这个桶中。
可以证明First Fit算法的结果不会超过最优结果的两倍。证明如下：

时间复杂度：O（n*log(n)）

代码实现：

//算法二  
#include<stdio.h>  
#include<vector>  
#include<ctime>  
using namespace std;  
const char path[17][30] = {"Data/Waescher_TEST0005.txt", "Data/Waescher_TEST0014.txt", "Data/Waescher_TEST0022.txt", "Data/Waescher_TEST0030.txt", "Data/Waescher_TEST0044.txt", "Data/Waescher_TEST0049.txt", "Data/Waescher_TEST0054.txt", "Data/Waescher_TEST0055A.txt", "Data/Waescher_TEST0055B.txt", "Data/Waescher_TEST0058.txt", "Data/Waescher_TEST0065.txt", "Data/Waescher_TEST0068.txt", "Data/Waescher_TEST0075.txt", "Data/Waescher_TEST0082.txt", "Data/Waescher_TEST0084.txt", "Data/Waescher_TEST0095.txt","Data/Waescher_TEST0097.txt"} ;   
int main() {  
    for (int t = 0; t < 17; ++t) {  
        clock_t start, end;  
        start = clock();  
        FILE* file = fopen(path[t], "r");  
        int numItems, capacity;  
        fscanf(file, "%d%d", &numItems, &capacity);  
        vector<int> items(numItems);   
        vector<int> buckets{capacity};//动态增长的桶数组   
        for (int i = 0; i < numItems; ++i) {  
            fscanf(file, "%d", &items[i]);  
            int j = 0;  
            for (; j < buckets.size(); ++j) {  
                if (buckets[j] > items[i]) {  
                    buckets[j] -= items[i];  
                    break;  
                }  
            }   
            if (j == buckets.size()) buckets.push_back(capacity - items[i]);  
        }  
        end = clock();  
        printf("test_file: %s, used %d bucket, running time: %lf seconds\n", path[t], buckets.size(), ((double)end - start) / CLK_TCK);  
    }  
}

(三) 排序+First Fit
将物品按照重量（Wj）从大到小排序，然后按First Fit算法的做法放入物品。
从最大的物品开始放的好处是最大化的利用空间。假设这样一种情况：桶的容量c是10，有三个物品的重量分别为4、1、6，如果按照物品这样的顺序将它们放入桶中，那么第一个桶会装下前两个物品，剩余容量5，第二个桶会装下最后一个物品，剩余容量4,；而如果先排序再放，那么第一个桶可以放下6和4，剩余容量0，第二个桶会放下1，剩余容量9。显然排序后的放法使得空间的利用率更大，如果这时要放第四个物品，只要物品重量超过5，第一种放法就要开第三个桶，而只有物品重量超过9第二种放法才需要开第三个桶。
另一个直观的理解是：先放大的物品，之后小的物品更有机会可以放到之前已经放有物品的桶中，也更有机会将桶填满或几乎填满；反过来，如果小的物品放在同一个桶中，剩余的大的物品又不能共同放入一个桶中，只能各开一个桶了，这就会产生很多剩有空间的桶，而这时可能已经没有小的物品可以用来填充了。

但这种算法不是最优的。还是举个例子，假设桶的容量还是10，现在有两个桶，分别存放了重量和为6、7的物品（注意每个桶中可能不止一件物品），然后接下来还有三个重量依次为3、2、2的物品要放入桶中，按照这个算法，最终会变成三个桶，分别是9、9、2，而最优放法应该是两个桶分别为10、10的。由于在放一个物品时无法考虑到后面的情况，只是找到第一个合适的位置便放，所以这个算法不是最优的。

时间复杂度：O（n*log(n)）
代码实现：

//算法三   
#include<stdio.h>  
#include<vector>  
#include<ctime>  
#include<algorithm>   
using namespace std;  
const char path[17][30] = {"Data/Waescher_TEST0005.txt", "Data/Waescher_TEST0014.txt", "Data/Waescher_TEST0022.txt", "Data/Waescher_TEST0030.txt", "Data/Waescher_TEST0044.txt", "Data/Waescher_TEST0049.txt", "Data/Waescher_TEST0054.txt", "Data/Waescher_TEST0055A.txt", "Data/Waescher_TEST0055B.txt", "Data/Waescher_TEST0058.txt", "Data/Waescher_TEST0065.txt", "Data/Waescher_TEST0068.txt", "Data/Waescher_TEST0075.txt", "Data/Waescher_TEST0082.txt", "Data/Waescher_TEST0084.txt", "Data/Waescher_TEST0095.txt","Data/Waescher_TEST0097.txt"} ;   
int main() {  
    for (int t = 0; t < 17; ++t) {  
        clock_t start, end;  
        start = clock();  
        FILE* file = fopen(path[t], "r");  
        int numItems, capacity;  
        fscanf(file, "%d%d", &numItems, &capacity);  
        vector<int> items(numItems);   
        vector<int> buckets{capacity};//动态增长的桶数组   
        for (int i = 0; i < numItems; ++i) {  
            fscanf(file, "%d", &items[i]);  
        }  
        sort(items.begin(), items.end(), [](int a, int b) {  
            return a > b;  
        });  
        for (int i = 0; i < numItems; ++i) {  
            int j = 0;  
            for (; j < buckets.size(); ++j) {  
                if (buckets[j] > items[i]) {  
                    buckets[j] -= items[i];  
                    break;  
                }  
            }   
            if (j == buckets.size()) buckets.push_back(capacity - items[i]);  
        }  
        end = clock();  
        printf("Ttest_file: %s, used %d bucket, running time: %lf seconds\n", path[t], buckets.size(), ((double)end - start) / CLK_TCK);  
    }  
}

(四) 元启发式算法（Greedy）
还是先将物品按重量从大到小排序，也还是维护一个桶的数组，不过这次不用First Fit，而是遍历所有桶，找到最合适的桶将物品放入。如果所有桶都不能满足，则新开一个桶并加到列表中去，并将当前物品放在这个桶中。
这种算法属于元启发式中的greedy范畴，一开始结果集合是空的，通过一步步构造来获得一个可行解。
这里需要定义什么是“最合适的桶”，最合适的桶需要满足以下条件：

该桶有剩余的空间存放当前的物品
与其他满足条件1的桶相比，该桶放入该物品后剩余的空间最小
简述以下条件2的合理性：选择放入该物品后剩余的空间最小的桶，从直观上讲，放入的那个桶的利用率是较高的；另一方面，没有被选择放入该物品的其他满足条件1的桶的剩余空间相比被选择的桶在放入物品之前的剩余空间要大，这使得接下来的物品能被放入已有的桶中的可能性较大。

时间复杂度：O（n2）
代码实现：

//算法四   
#include<stdio.h>  
#include<vector>  
#include<ctime>  
#include<algorithm>   
using namespace std;  
const char path[17][30] = {"Data/Waescher_TEST0005.txt", "Data/Waescher_TEST0014.txt", "Data/Waescher_TEST0022.txt", "Data/Waescher_TEST0030.txt", "Data/Waescher_TEST0044.txt", "Data/Waescher_TEST0049.txt", "Data/Waescher_TEST0054.txt", "Data/Waescher_TEST0055A.txt", "Data/Waescher_TEST0055B.txt", "Data/Waescher_TEST0058.txt", "Data/Waescher_TEST0065.txt", "Data/Waescher_TEST0068.txt", "Data/Waescher_TEST0075.txt", "Data/Waescher_TEST0082.txt", "Data/Waescher_TEST0084.txt", "Data/Waescher_TEST0095.txt","Data/Waescher_TEST0097.txt"} ;   
int main() {  
    for (int t = 0; t < 17; ++t) {  
        clock_t start, end;  
        start = clock();  
        FILE* file = fopen(path[t], "r");  
        int numItems, capacity;  
        fscanf(file, "%d%d", &numItems, &capacity);  
        vector<int> items(numItems);   
        vector<int> buckets{capacity};//动态增长的桶数组   
        for (int i = 0; i < numItems; ++i) {  
            fscanf(file, "%d", &items[i]);  
        }  
        sort(items.begin(), items.end(), [](int a, int b) {  
            return a > b;  
        });  
        for (int i = 0; i < numItems; ++i) {  
            int j = 0, choose = -1;  
            for (; j < buckets.size(); ++j) {  
                if (buckets[j] > items[i] && (choose == -1 || buckets[j] < buckets[choose]))   
                    choose = j;  
            }   
            if (choose == -1) buckets.push_back(capacity - items[i]);  
            else buckets[choose] -= items[i];  
        }  
        end = clock();  
        printf("test_file: %s, used %d bucket, running time: %lf seconds\n", path[t], buckets.size(), ((double)end - start) / CLK_TCK);  
    }  
}

(五) 遍历物品依次装填箱子1
还是现将物品按重量从大到小排序，不过不同于前面算法，前面的算法都是对每一个物品遍历所有桶直到找到合适的桶，这个算法反过来，对每一个桶遍历所有物品，遇到重量小于桶的剩余容量的物品则将其装入桶中，直到桶不能再放下任何其他一个物品为止。每一轮装填一个桶，直到所有物品都被装入桶中为止。
前面的算法中存放物品的数据结构一般用数组即可，而在这个算法中，物品不再按照顺序被取出，可能会取出列表中某一个位置的物品，所以用数组的话当数据量比较大时删除的开销较大，用链表list会比较合适。
这个算法中由于只需考虑当前的桶，所以无需再维护一个桶的动态数组。
同样的，先装大的物品有利于提高空间利用率，而提高空间利用率往往也意味着需要用到更少的桶。

时间复杂度：O（n*log(n)）
代码实现：

//算法五   
#include<stdio.h>    
#include<vector>   
#include<ctime>    
#include<algorithm>  
#include<list>    
using namespace std;    
const char path[17][30] = {"Data/Waescher_TEST0005.txt", "Data/Waescher_TEST0014.txt", "Data/Waescher_TEST0022.txt", "Data/Waescher_TEST0030.txt", "Data/Waescher_TEST0044.txt", "Data/Waescher_TEST0049.txt", "Data/Waescher_TEST0054.txt", "Data/Waescher_TEST0055A.txt", "Data/Waescher_TEST0055B.txt", "Data/Waescher_TEST0058.txt", "Data/Waescher_TEST0065.txt", "Data/Waescher_TEST0068.txt", "Data/Waescher_TEST0075.txt", "Data/Waescher_TEST0082.txt", "Data/Waescher_TEST0084.txt", "Data/Waescher_TEST0095.txt","Data/Waescher_TEST0097.txt"} ;   
int main() {    
    for (int t = 0; t < 17; ++t) {  
        clock_t start, end;    
        start = clock();    
        FILE* file = fopen(path[t], "r");  
        int numItems, capacity;  
        fscanf(file, "%d%d", &numItems, &capacity);    
        list<int> items;    
        int item;  
        int remain, numBuckets = 0; //当前桶剩余的容量，桶的总个数   
        for (int i = 0; i < numItems; ++i) {    
            fscanf(file, "%d", &item);   
            items.push_back(item);  
        }    
        items.sort([](int a, int b) {    
            return a > b;    
        });    
        list<int>::iterator it;  
        while(!items.empty()) {  
            remain = capacity;  
            for (it = items.begin(); it != items.end(); ) {  
                if (*it < remain) {  
                    remain -= *it;   
                    if (remain < items.back()) break;//如果桶连最小的物品都放不下，那么就没有可以继续放下的物品了  
                    it = items.erase(it);   
                }  
                else ++it;  
            }  
            numBuckets++;  
        }  
        end = clock();    
        printf("test_file: %s, used %d bucket, running time: %lf seconds\n", path[t], numBuckets, ((double)end - start) / CLK_TCK);    
    }     
}

(六) 遍历物品依次装填箱子2（大小搭配/双指针）
如果物品们的重量由大到小分布较为均匀的话，可以尝试使用这个算法。
依然是遍历物品装填箱子，对于每一个待装填的箱子，我们不再是从头遍历所有物品，而是先取出当前列表中最大的物品，接着取出当前列表中最小的物品，将它们放在同一个箱子中，然后由小到大判断这个箱子是否还能装下其它物品。
使用这样的装箱方法是有原因的，就像高斯在计算1加到100时运用的两端分别相加的方法一样，我们可以期望大和小的搭配可以使得每个箱子都达到或接近被填满。

时间复杂度：O（n*log(n)）
代码实现：

//算法六   
#include<stdio.h>  
#include<vector>  
#include<ctime>  
#include<algorithm>   
using namespace std;  
const char path[17][30] = {"Data/Waescher_TEST0005.txt", "Data/Waescher_TEST0014.txt", "Data/Waescher_TEST0022.txt", "Data/Waescher_TEST0030.txt", "Data/Waescher_TEST0044.txt", "Data/Waescher_TEST0049.txt", "Data/Waescher_TEST0054.txt", "Data/Waescher_TEST0055A.txt", "Data/Waescher_TEST0055B.txt", "Data/Waescher_TEST0058.txt", "Data/Waescher_TEST0065.txt", "Data/Waescher_TEST0068.txt", "Data/Waescher_TEST0075.txt", "Data/Waescher_TEST0082.txt", "Data/Waescher_TEST0084.txt", "Data/Waescher_TEST0095.txt","Data/Waescher_TEST0097.txt"} ;   
int main() {  
    for (int t = 0; t < 17; ++t) {  
        clock_t start, end;  
        start = clock();  
        FILE* file = fopen(path[t], "r");  
        int numItems, capacity;  
        fscanf(file, "%d%d", &numItems, &capacity);  
        vector<int> items(numItems);   
        int remain, numBuckets = 0; //当前桶剩余的容量，桶的总个数   
        for (int i = 0; i < numItems; ++i) {  
            fscanf(file, "%d", &items[i]);  
        }  
        sort(items.begin(), items.end(), [](int a, int b) {  
            return a > b;  
        });  
        int left = 0, right = items.size() - 1;  
        while (left <= right) {  
            remain = capacity;  
            remain -= items[left++];  
            while(left <= right && remain > items[right]) remain -= items[right--];  
            numBuckets++;  
        }  
        end = clock();  
        printf("test_file: %s, used %d bucket, running time: %lf seconds\n", path[t], numBuckets, ((double)end - start) / CLK_TCK);  
    }  
}

(七) 模拟退火
不同于算法四中的贪心算法，模拟退火是一个迭代的元启发式算法。简单地说，模拟退火是针对在Local Search中可能产生的局部优化作了修改，不像Local Search只选择更好的值作为下一个状态，模拟退火在高温时会有比较大的可能接受比当前值差的值，直到低温时才逐渐趋于稳定。这样就有效避免了看不见“一山更比一山高”的情况。
首先要有一个初始的状态，即每个物品分别被放到哪个桶中。可以用直接法的结果作为初始状态，选这个的原因是它比较简单，而且比较有优化的空间。
然后问题就来了，如何由当前状态产生下一个状态？如何判断当前状态与下一个状态哪个比较好？
如果目标函数是根据当前状态计算桶的个数，会有很多种状态计算的结果相同，这些状态之间又该如何比较？
简单起见，状态的比较可以考虑以下四种方案：

目标函数是根据当前状态计算桶的个数，如果有相同的结果，随机选择一个
结合广度搜索，目标函数是根据当前状态计算桶的个数，如果有相同的结果，按比例随机选择几个进行递归，取最好的结果。
目标函数分为两部分，分别计算当前状态对应的桶的个数，以及物品的分布均匀程度。比较两种状态时先比较桶的个数，如果桶的个数相同，则选择分布比较不均匀的一种状态。因为分布比较不均匀代表着有的桶装得多有的桶装得少，那么这些桶之间可能就可以合并。
与(3)差不多，不过桶个数相同时选择分布比较均匀的状态。

状态的切换则考虑以下两种方案：

选择一个桶，将其中的一个物品放到另一个桶中
选择两个桶，彼此间交换一个物品

综上，确定这样一个算法：

使用直接法的结果作为初始状态
每次迭代中随机选择一个桶，将其中的一个物品放到另一个合适的桶中（物品的放置采用First Fit），作几次这样的操作，选择其中最好的状态与当前状态比较。如果其中最好的状态比当前状态差，且概率上没有被选择，这样的情况连续出现多次则结束迭代，当前状态为最终结果。
状态间的比较采用第三种方案，计算分布均匀程度可以通过先计算每个桶存放物品的重量与平均桶存放物品的重量的差的绝对值，然后求所有桶的这个值的平均数来表示。这个平均数越大则说明分布越不均匀。
对不好的状态是否采用根据温度来判断，采用的概率为
e-t/T
t是一个预先定义好的常数。（控制采用的概率在0.01~0.4之间）
温度在每次迭代时乘以一个小于1的系数，当温度低于某个值时结束迭代

代码实现：

#include<stdio.h>  
#include<vector>  
#include<time.h>  
#include<stdlib.h>   
#include<numeric>  
#include<math.h>  
#include<numeric>  
#define NEIGHBOUR_COUNT 20  
#define MAX_NO_CHANGE 10  
using namespace std;  
  
const double T = 500, T_min = 100, dec_rate = 0.999;//初始温度,最低温度和下降的乘系数  
const double divider = 450.0;   
const char path[17][30] = {"Data/Waescher_TEST0005.txt", "Data/Waescher_TEST0014.txt", "Data/Waescher_TEST0022.txt", "Data/Waescher_TEST0030.txt", "Data/Waescher_TEST0044.txt", "Data/Waescher_TEST0049.txt", "Data/Waescher_TEST0054.txt", "Data/Waescher_TEST0055A.txt", "Data/Waescher_TEST0055B.txt", "Data/Waescher_TEST0058.txt", "Data/Waescher_TEST0065.txt", "Data/Waescher_TEST0068.txt", "Data/Waescher_TEST0075.txt", "Data/Waescher_TEST0082.txt", "Data/Waescher_TEST0084.txt", "Data/Waescher_TEST0095.txt","Data/Waescher_TEST0097.txt"} ;   
int sum;//物品重量和  
int numItems, capacity;//物品数量，桶容量   
//计算当前状态对应的桶的均匀分布程度
double get_avg(vector<vector<int>>& buckets) {  
    double aavg = (double)sum / buckets.size();  
    double temp = 0;  
    for (vector<int> bucket : buckets) {  
        temp += abs(accumulate(bucket.begin(), bucket.end(), 0) - aavg);  
    }  
    return temp / buckets.size();  
}  
//将下标为from的桶中某一个元素移动到其他桶中，产生邻居状态
vector<vector<int>> do_change(vector<vector<int>> buckets, int from) {  
    int random = rand() % buckets[from].size();  
    int j = 0;  
    for (; j < buckets.size(); ++j) if (j != from){  
        if (capacity - accumulate(buckets[j].begin(), buckets[j].end(), 0) > buckets[from][random]) {  
            //printf("from %d's %d ", from, buckets[from][random]);  
            //printf("to %d\n", j);  
            buckets[j].push_back(buckets[from][random]);  
            break;  
        }  
    }   
    if (j != buckets.size()) {//物品顺利地放到其它桶中   
        buckets[from].erase(buckets[from].begin() + random);  
        if (buckets[from].empty()) buckets.erase(buckets.begin() + from);  
    }  
    return buckets;  
}  
int main() {  
    srand((int)time(NULL));  
    for (int t = 0; t < 17; ++t) {  
        clock_t start, end;  
        start = clock();  
        FILE* file = fopen(path[t], "r");  
        fscanf(file, "%d%d", &numItems, &capacity);  
        int item;//临时的item变量   
        vector<vector<int>> buckets{{}};  
        int remain = capacity;   
        //按照直接法得到初始状态   
        sum = 0;  
        for (int i = 0; i < numItems; ++i) {  
            fscanf(file, "%d", &item);  
            sum += item;  
            if (remain > item) {  
                remain -= item;  
                buckets.back().push_back(item);  
            }  
            else {  
                remain = capacity - item;  
                buckets.push_back({item});  
            }  
        }  
        //初始状态已经存在buckets里  
        //开始迭代    
        double temperature = T;  
        int count = 0;  
        int no_change = 0;  
        while(temperature > T_min) {//达到最低温即退出   
            count++;  
            int bucket_count = buckets.size();  
            double average = get_avg(buckets);  
            vector<vector<int>> next_best;//选择最好的下一个状态   
            for (int i = 0; i < NEIGHBOUR_COUNT; ++i) {  
                int next_best_count = next_best.size();  
                double next_best_average = get_avg(next_best);  
                int from = rand() % buckets.size();  
                vector<vector<int>> res = do_change(buckets, from);  
                //计算修改后的状态对应的桶的个数、分布均匀程度  
                int count = res.size();  
                if (i == 0 || count < next_best_count || count == next_best_count && get_avg(res) > next_best_average) {  
                    next_best = res;  
                }  
                  
            }  
            //将最好的下一个状态与当前状态比较  
            int next_best_count = next_best.size();  
            if (next_best_count < bucket_count ||   
                next_best_count == bucket_count && get_avg(next_best) > average) {  
                    no_change = 0;  
                    buckets = next_best;  
                }  
                  
            //如果最好的下一个状态比当前状态差，则根据概率决定是否选择下一个状态  
            else {  
                double rate = exp(-divider / temperature);  
                int random = rand() % 100;  
                if (random < rate * 100) {  
                    buckets = next_best;  
                    no_change = 0;  
                }  
                else if (++no_change > MAX_NO_CHANGE) break;  
            }  
            temperature *= dec_rate;  
              
               
        }   
        end = clock();  
        printf("iteration count: %d, temperature: %f\n", count, temperature);  
//      for (vector<int>& vec : buckets) {  
//          count += vec.size();  
//          for (int it : vec) printf("%d ", it);  
//          printf("\n");  
//      }  
          
        printf("test file: %s, used %d buckets, running time: %lf seconds\n", path[t], buckets.size(), ((double)end - start) / CLK_TCK);  
    }  
}

三、算法结果分析与比较

从总体上看，这些数据有点太弱，导致除了模拟退火算法其它算法的运行时间都没有达到1毫秒，所以时间上没法怎么比较，唯一的办法可能就是对同一数据重复计算10次、100次取其时间和，这里就不做了。
而且由于给出的数据中物品重量默认是从大到小排好序的，所以排序与否对结果没有什么影响。
主要作以下几组比较：
(一) 算法一与算法二
可以发现，First Fit算法显然是优于直接法的，这与预期相符，因为First Fit充分利用了前面已经装填过物品的桶的剩余空间。

(二) 算法二和算法三
如前面所说，由于给出的数据本身就是排好序的，所以这两个算法的结果相同。
(三) 算法三与算法四
在所有测试用例中两种算法的结果都相同，这与预期不太相同，我们预期中算法四是要更优于算法三的，因为它选择能放下物品的剩余容量最小的桶，提高了利用率。不过可能是给出的数据没有出现在算法三中讨论到的情况，所以体现不出算法四的优势。

(四) 算法三与算法五
这两个算法分别从不同的角度切入问题，算法三是按物品的顺序放的，而算法五是按桶的顺序放的，两者各有千秋，不过从给定数据的结果来看，算法三似乎比算法五略好一些。

(五) 算法五与算法六
同样是按桶的顺序放置物品，不同的地方是算法五只有一个指针从左往右扫描物品，算法六则有两个指针分别从两端向中间扫描。
从时间复杂度上看显然是算法六更好的，因为它是线性复杂度。
从给定数据的运行结果上看，大多数时候是算法五更好，但也有算法六比较好的情况（在图中用黄色背景标出的部分）。

(六) 算法七与其他算法
从结果上看，算法七（模拟退火）的结果与算法二相同。
模拟退火在迭代次数较少时结果具有不确定性，我通过增加每次迭代的可选邻居状态数量和减少温度下降的速率来增加迭代次数，发现最终的结果会趋于一个稳定值，不再随参数的改变而改变，这个值与算法二产生的值相同。所以我估计算法二对于这些测例产生的结果应该是很接近于最优解的。
因为多次迭代以及许多函数调用，所以算法七运行时间会比其他算法长。

另外，由于对算法七中比较两个状态好坏时用均匀分布程度为依据只是直接地推论，并没有严密的证明，所以我专门做了一个对比实验。分别在桶个数相同的情况下选择均匀分布程度较高和较低的状态，两种情况作比较，结果发现选择均匀分布情况较低的状态的算法最终产生的结果是比较好的，这也在某种程度上证明了算法七的正确性。

码农公寓

Bin Packing Problem

一、 问题描述

二、 算法介绍及实现

三、 算法结果分析与比较

相关文章

一、问题描述

二、算法介绍及实现

三、算法结果分析与比较