algorithm - 分支定界实现

我一直在研究这个问题，我可以得到一些结果，但是在这里实现分支绑定方法有困难。
你们能帮我吗？
建造仓库
说明
中奖后，你决定
买几辆卡车。
你的目标是把货物交给所有人
科英布拉的超市。但现在你
必须建立仓库来储存
货物，你得考虑一下
可能的地点。理想情况下，
仓库应靠近
超市为了减少
运输成本。但是，你
不能把所有的钱都花在建筑上
到处都是仓库，所以你必须
做出明智的决定：考虑到
每个仓库的固定成本
在每个可能的地点
每项服务的运输成本
超市从各个地点
接下来的5年，你想知道
应建造仓库，以便
总成本（运输和固定
成本）在这段时间内是最低的。
注意至少有一个仓库必须
建造。此外，计算
总的运输成本必须
考虑到这一切
必须为超市提供服务。
输入
每个测试用例都包含信息
关于建筑的固定成本
指定地点的仓库和
运输成本
地点和超市第一次
每个测试用例的行给出
可能的地点数量
可以建造仓库（n超市数量（m下面n行中的每一行给出
建造仓库的成本
地点和交通
与供应每个
在M超市里
地点。
输出
产出是最低的总成本
建造和运营
仓库（整数）。例子
输入：
4 5个
10 8 6 10 8 10
9 1 2 10 4 8
10 6 4 2 1 5
1 10 4 6 9 3
输出：
二十六
http://pastebin.com/apXCMdxy

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

struct set {
    int *nodes;
    int position;
    int size;
    int capacity;
};

int locations;
int supermarkets;





void calc_custo(int **matrix, struct set *set, int *lower){


    int i;
    int last;
    int cost;
    int t;
    int j;
    int *mins;
    struct set *new_set;
    new_set = malloc(sizeof(struct set));
    new_set->nodes = malloc(new_set->capacity * sizeof(int));

    mins = malloc((supermarkets + 1) * sizeof(int));
    /*
    for (i = 0; i < set->size; i ++) {
        printf("%d ", set->nodes[i]);
    }
    printf("\n");*/
    for(j = 0; j < supermarkets + 1; j++) {
        mins[j] = INT_MAX;
    }

    cost = 0;
    for(i = 0; i < set->size; i ++) {
        t = set->nodes[i];
        cost += matrix[t][0];
         for(j = 1; j < supermarkets + 1; j++) {
             if (mins[j] > matrix[t][j]) {
                 mins[j] = matrix[t][j];
             }

         }
    }

    for(j = 1; j < supermarkets + 1; j++) {
        cost += mins[j];
    }

    free(mins);

    memcpy(new_set, set, sizeof(struct set));
    memcpy(new_set->nodes, set->nodes, set->capacity * sizeof(int));

    if (cost < *lower) {
        *lower = cost;

    }

    if (set->position < set->capacity) {
        set->nodes[set->size] = set->position;
        set->size++;
        set->position++;
        calc_custo(matrix, set, lower);

    }

    if (new_set->position < new_set->capacity) {
        new_set->nodes[new_set->size - 1] = new_set->position;
        new_set->position++;
        calc_custo(matrix, new_set, lower);
    }

}


int main (int argc, const char* argv[])
{


    int t;
    int i, j;
    int lower;
    int **matrix;

    /*allocat matrix*/

    scanf("%d", &locations);
    scanf("%d", &supermarkets);

    matrix = malloc(locations * sizeof(int*));
    for (i = 0; i < locations; i++){
        matrix[i] = malloc((supermarkets + 1) * sizeof(int));

    }

    struct set *set;
    set = malloc(sizeof(struct set));
    set->nodes = malloc(locations * sizeof(int));
    set->size = 1;
    set->position = 1;
    set->capacity = locations;
    set->nodes[0] = 0;

    for (i = 0; i < locations; i++) {
        for (j = 0; j < supermarkets + 1; j++) {
            scanf("%d", &t);
            matrix[i][j] = t;
        }
    }
    lower = INT_MAX;
    calc_custo(matrix, set, &lower);
    printf("%d\n", lower);
    return 0;
}

最佳答案

我不清楚标准的分支和绑定是否会在这里工作。
bnb的工作原理是，当s的任何扩展到一个完整解的成本不能提高到目前为止找到的最佳完整解的成本时，迫使search回溯到到达一个部分解s。这取决于是否能够对任何部分解的成本的下界进行讨论。
在这个问题中，对部分解决方案s的一步扩展既可以提高总成本，也可以降低总成本（如果它使向超市交货的成本比建造额外仓库的成本低），这使得下界语句很难以有用的方式陈述。

关于algorithm - 分支定界实现，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5287686/