私はこの問題に取り組んでおり、いくつかの結果を得ることができますが、ここで分岐とバインドの方法を実装するのに問題があります。
皆さん、私を助けてくれますか?
建物の倉庫
説明
After winning the lottery, you decide to buy several truks (or lorries). Your goal is to deliver goods to all supermarkets in Coimbra. But now you have to build warehouses to store the goods, and you have to think about possible locations. Ideally, the warehouses should be located close to the supermarkets in order to reduce transportation costs. However, you cannot spend all the money on building warehouses everywhere, so you have to make a clever decision: given the fixed cost of building each warehouse in each possible location and the transportation cost of serving each supermarket from each location in the next 5 years, you want to know where warehouses should be build so that the overall cost (transportation and fixed costs) over that period is minimum. Note that at least one warehouse must be built. Moreover, the computation of the overall transportation cost has to take into account that all supermarkets must be served.
入力
各テスト ケースには、特定の場所に倉庫を建設するための固定費と、各場所とスーパーマーケットに関連する輸送費に関する情報が含まれています。各テスト ケースの最初の行は、倉庫を建設できる可能性のある場所の数 (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
出力:
26
#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;
}