Ветвь и связанная реализация

Question

Я работал над этой проблемой и могу получить некоторые результаты, но у меня возникают проблемы с реализацией метода ветвления и привязки здесь.
Ребята, вы можете мне помочь?

Строительные Склады

Описание

После выигрыша в лотерею вы решаете купить несколько грузовиков (или грузовиков). Ваша цель - доставить товар во все супермаркеты Коимбры. Но теперь вам нужно построить склады для хранения товаров, и вам нужно подумать о возможных местах. В идеале, склады должны быть расположены рядом с супермаркетами, чтобы снизить транспортные расходы. Однако вы не можете потратить все деньги на строительство складов повсюду, поэтому вам нужно принять умное решение: учитывая фиксированную стоимость строительства каждого склада в каждом возможном месте и транспортные расходы на обслуживание каждого супермаркета из каждого места в течение следующих 5 лет. Вы хотите знать, где должны быть построены склады, чтобы общие затраты (транспортные и фиксированные) за этот период были минимальными. Обратите внимание, что должен быть построен как минимум один склад. Кроме того, при расчете общей стоимости перевозки необходимо учитывать, что все супермаркеты должны обслуживаться.

вход

Каждый тестовый пример содержит информацию о фиксированных затратах на строительство складов в определенных местах и ​​транспортных расходах, связанных с каждым местом и супермаркетом. В первой строке каждого контрольного примера указано количество возможных мест, где может быть построен склад (n<51), и количество супермаркетов (m < 16). Затем в каждой из следующих 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

Ouput:

26

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;
}

Answer 1

Мне не ясно, что стандартная ветвь-и-граница будет работать здесь.

BnB работает, заставляя поиск отказаться от достижения частичного решения s, когда стоимость любого расширения s до полного решения не может улучшить стоимость лучшего полного решения, найденного до сих пор. Это зависит от способности сказать что-то о нижней границе стоимости любого частичного решения, s.

В этой проблеме одношаговое расширение до частичного решения может либо повысить общую стоимость, либо снизить ее (если это делает доставку в супермаркеты дешевле, чем стоимость строительства дополнительного склада), что затрудняет утверждение о нижней границе изложить в полезной форме.

Answer 2

Ответ Рэйфа верный - "простые" B&B здесь не сработают, так как счет может увеличиваться или уменьшаться. Но в этой проблеме все еще есть некоторая структура, которую можно использовать.

Любой непустой набор складов дает (возможно, неоптимальное) решение. Общая стоимость данного решения - это стоимость строительства всех складов плюс стоимость обслуживания всех супермаркетов. Учитывая набор складов, очевидно, что каждый супермаркет должен обслуживаться складом минимальной стоимости для этого супермаркета. Обратите внимание, что при добавлении складов к решению стоимость обслуживания данного склада либо остается неизменной, либо уменьшается.

Следует отметить, что в решение не стоит добавлять склад, если это увеличивает общую стоимость. Зачем?

1. Если это последний склад, добавленный к решению, то очевидно, что он увеличивает общую стоимость и поэтому не должен добавляться.
2. В противном случае, предположим, что это i-е из k > i складов, добавленных в решение. Рассмотрим решение, которое мы получили бы, добавив его на последнем месте вместо i-го места - может ли добавление этого склада затем снизить общую стоимость? Нет, потому что для каждого супермаркета каждый склад, добавленный на этапах i+1 .. k, либо снижает стоимость обслуживания, либо оставляет его прежним. Единственный способ, которым добавление склада может привести к чистой прибыли, - это возможность обслуживать один или несколько супермаркетов дешевле, чем текущее решение. Если после добавления первых шагов i-1 это не так, то после добавления всех других складов k-1 в полное решение этого не произойдет. Это означает, что чистая стоимость добавления склада в более позднее время всегда равна или хуже, чем добавление в более раннее время.

Это может сократить дерево поиска настолько, чтобы простая рекурсия завершилась достаточно быстро.