Я работал над этой проблемой и могу получить некоторые результаты, но у меня возникают проблемы при реализации метода ветвления и привязки здесь.
Ребята, вы можете мне помочь?
Строительные склады
Описание
После выигрыша в лотерею вы решаете
купить несколько грузовиков (или грузовиков).
Ваша цель - доставить товар всем
супермаркеты в Коимбре. Но теперь ты
должны построить склады для хранения
товары, и вы должны думать о
возможные места. В идеале
склады должны быть расположены близко к
супермаркеты, чтобы уменьшить
транспортные расходы. Тем не менее, вы
не может потратить все деньги на строительство
склады везде, так что вы должны
принять умное решение: учитывая
фиксированная стоимость строительства каждого склада
в каждом возможном месте и
Транспортная стоимость обслуживания каждого
супермаркет из каждого места в
следующие 5 лет, вы хотите знать, где
склады должны быть построены так, чтобы
общая стоимость (транспортная и фиксированная
расходы) в течение этого периода является минимальным.
Обратите внимание, что хотя бы один склад должен
быть построенным Кроме того, вычисление
общая стоимость перевозки должна
принять во внимание, что все
супермаркеты должны быть обслужены.
Input
Каждый тестовый набор содержит информацию
о постоянных затратах на строительство
склады в указанных местах и
транспортные расходы, связанные с каждым
расположение и супермаркет. Первый
строка каждого теста дает
количество возможных мест, где
склад может быть построен (n <51) и
количество супермаркетов (м <16). Затем,
каждая из следующих n строк дает
стоимость строительства склада по
это место и транспорт
расходы, связанные с поставкой каждого
м супермаркетов из этого
место. </p>
выход
На выходе получается минимальная общая стоимость
строительства и эксплуатации
склады (целое число). Пример
Введите:
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;
}