問(wèn)題描述

給定n個(gè)設(shè)備和m個(gè)顧客

• 每個(gè)顧客有一定的需求(demand)需要被設(shè)備滿足，記為d[i]
• 每個(gè)設(shè)備有不同的滿足顧客需求的容量(capacity)，記為c[j]
• 每個(gè)設(shè)備有不同的開(kāi)啟費(fèi)用(opening cost)，記為o[j]
• 不同顧客分配到不同設(shè)備會(huì)有不同的分配費(fèi)用(assignment cost)，記為a[i][j]

現(xiàn)在所要達(dá)成的目的是要滿足所有顧客的要求，同時(shí)使opening cost和assignment cost的總和(total cost)最小。問(wèn)：

1. 最終哪些設(shè)備要開(kāi)啟？
2. 對(duì)所有顧客的最終分配方案是怎么樣的？

分析

m個(gè)顧客會(huì)有n中不同的選擇，如果我們要窮盡所有的可能，時(shí)間復(fù)雜度將會(huì)是 O(n^m)，顯然這不是一個(gè)很好的選擇；所以我們應(yīng)該采取更優(yōu)的做法。

首先先寫(xiě)出主程序框架:

int main(){

    for(int testCase = 1; testCase <= 71; testCase ++){

        // Data declaration
        int n, m;   // n facilities, m customers
        int* d;     // demands of customers
        int* c;     // capacities of facilities
        int* o;     // opening cost of facilities
        int** a;    // assignment cost for each (cus, fac)

        bool* open_state;   // result: open state of facilities
        int* assign_state;  // result: assignment of cus->fac
        
        // Load files
        ifstream infile;
        char filename[32];
        sprintf_s(filename, "Instances\\p%d", testCase);
        infile.open(filename, ios::in);

        if(!infile.is_open ()){
            cout << "Open file failure: " << filename <<  endl;
            continue;
        }

        infile >> n >> m;
        c = new int[n];
        o = new int[n];
        for(int i = 0; i < n; ++i){
            infile >> c[i] >> o[i]; 
        }
        d = new int[m];
        a = new int*[m];
        for(int i = 0; i < m; ++i){
            a[i] = new int[n];
            infile >> d[i];
        }

        for(int i = 0; i < m; ++i){
            for(int e = 0; e < n; ++e){
                infile >> a[i][e];
            }
        }
        infile.close();

        open_state = new bool[n];
        for(int i = 0; i < n; ++i) open_state[i] = false;
        assign_state = new int[m];
        
        // Calculate
        int result = Algorithm(n,m,d,c,o,a,open_state,assign_state);

        // Output Results
        sprintf_s(filename, "results\\greedy\\p%d", testCase);
        ofstream outfile(filename);
        if(result == -1){
            outfile << "No result" << endl;
            continue;
        }
        outfile << result << endl;
        for(int i = 0; i < n; ++i)
            outfile << open_state[i] << ' ';
        outfile << endl;
        for(int i = 0; i < m; ++i)
            outfile << assign_state[i] << ' ';
        outfile << endl;

        // Release space
        for(int i = 0; i < m; ++i){
            delete[] a[i];
        }
        delete[] c, o, open_state, assign_state;
    }
}

貪心算法

首先比較容易想到的是貪心算法。按照逐個(gè)顧客分配的辦法，每次為顧客進(jìn)行分配的時(shí)候，需要找到為他分配設(shè)備的最小花費(fèi)，這有可能是：

• 無(wú)需重新分配新的設(shè)備，花費(fèi)總額為 a[i][j]
• 分配新的設(shè)備，花費(fèi)總額為 c[j]+a[i][j]

值得一提的是，貪心算法大概率不是最優(yōu)算法，甚至有可能會(huì)有在原本有解的情況下算出無(wú)解的答案。但其優(yōu)點(diǎn)是會(huì)比較快。

#include <iostream>
#include "greedy.hpp"
using namespace std;

int Greedy(int n, int m, int *d, int *c, int *o, int **a, bool *os, int* as){

    int tc = 0;
    for(int curCus = 0; curCus != m; ++curCus){
        int minCost = INT32_MAX;
        int curChoice = -1;
        for(int curFac = 0; curFac != n; curFac++){
            if(d[curCus] <= c[curFac]){
                int tempCost = a[curCus][curFac];
                tempCost += os[curFac] ? 0 : o[curFac];
                if(tempCost < minCost){
                    minCost = tempCost;
                    curChoice = curFac;
                }
            }
        }
        if(curChoice == -1)
            return -1;
        
        os[curChoice] = true;
        as[curCus] = curChoice;
        c[curChoice] -= d[curCus];
        tc += minCost;
    }
    return tc;
}

運(yùn)算結(jié)果：

具體的分配結(jié)果可見(jiàn)github倉(cāng)庫(kù)

貪心算法V1

在上面的算法中，我們?nèi)?code>p1的結(jié)果為例:

18076
1 1 1 1 0 1 1 0 1 1 
1 1 1 8 1 9 8 9 8 9 9 9 9 9 9 9 5 9 9 5 5 5 5 5 5 5 5 5 5 0 3 0 5 0 3 0 0 3 0 0 0 3 3 3 8 3 3 2 2 6 

我們可以發(fā)現(xiàn)使用貪心算法，顧客傾向于不開(kāi)新的設(shè)備，因?yàn)樾麻_(kāi)設(shè)備要加上開(kāi)設(shè)備的費(fèi)用。可以理解到，每個(gè)顧客都把開(kāi)某個(gè)設(shè)備的費(fèi)用算到了自己頭上，就像滾燙的山芋不愿意握在手上；但實(shí)際上開(kāi)設(shè)備的費(fèi)用最終是落到總費(fèi)用上，所以我們可以試一下顧客不去考慮開(kāi)工廠的費(fèi)用，到最后再去算。

代碼和上面類似V1版本的類似，只有一些細(xì)微的修改

// 刪去這行
tempCost += os[curFac] ? 0 : o[curFac];
// 增加這個(gè)
if(!os[curChoice]){
    minCost += o[curChoice];
    os[curChoice] = true;
}

結(jié)果：