#include <iostream>
#include <sstream>
void show(std::string message, int **Emas, int *storage, int *shop, int storageSize, int shopSize){
std::cout << message;
//printf("\t");
for(int i = 0; i < shopSize; i++){
printf("\t[%i]", shop[i]);
}
printf("\n");
for(int i = 0; i < storageSize; i++){
printf("[%i]:", storage[i]);
for(int j = 0; j < shopSize; j++){
printf("\t%i", Emas[i][j]);
}
printf("\n");
}
printf("\n");
}
int NorthWest(int *storage1, int *shop1, int shopSize, int storageSize, int **emptyMas, int **mas){
int *storage = (int*)malloc(storageSize * sizeof(int));
int *shop = (int*)malloc(shopSize * sizeof(int));
for ( int i = 0; i < storageSize; i++)
storage[i] = storage1[i];
for ( int i = 0; i < shopSize; i++)
shop[i] = shop1[i];
int storageIndex = 0, shopIndex = 0, sum = 0;
while ((storageIndex < storageSize) && (shopIndex < shopSize)){
if (storage[storageIndex] > shop[shopIndex]){
emptyMas[storageIndex][shopIndex] = shop[shopIndex];
storage[storageIndex] -= shop[shopIndex];
sum += mas[storageIndex][shopIndex] * emptyMas[storageIndex][shopIndex];
shopIndex++;
}
else {
emptyMas[storageIndex][shopIndex] = storage[storageIndex];
shop[shopIndex] -= storage[storageIndex];
sum += mas[storageIndex][shopIndex] * emptyMas[storageIndex][shopIndex];
storageIndex++;
}
}
free(shop);
free(storage);
return sum;
}
int MinPrice(int *storage1, int *shop1, int shopSize, int storageSize, int **emptyMas, int **mas){
int *storage = (int*)malloc(storageSize * sizeof(int));
int *shop = (int*)malloc(shopSize * sizeof(int));
for ( int i = 0; i < storageSize; i++)
storage[i] = storage1[i];
for ( int i = 0; i < shopSize; i++)
shop[i] = shop1[i];
int sum = 0, nmiI = 0, nmiJ = 0, i = 0, j = 0;
bool flag = true;
bool *I = (bool*)calloc(storageSize, sizeof(bool));
bool *J = (bool*)calloc(shopSize, sizeof(bool));
while (flag){
flag = false;
for ( i = 0; i < storageSize; i++){
if(!I[i]){
nmiI = i;
break;
}
}
for ( i = 0; i < shopSize; i++){
if (!J[i]){
nmiJ = i;
break;
}
}
for ( i = 0; i < storageSize; i++){
for ( j = 0; j < shopSize; j++){
if (mas[nmiI][nmiJ] >= mas[i][j] && !I[i] && !J[j]){
nmiI = i;
nmiJ = j;
flag = true;
}
}
}
if (flag){
if(storage[nmiI] > shop[nmiJ]){
emptyMas[nmiI][nmiJ] = shop[nmiJ];
storage[nmiI] -= shop[nmiJ];
sum += mas[nmiI][nmiJ] * emptyMas[nmiI][nmiJ];
J[nmiJ] = true;
}
else{
emptyMas[nmiI][nmiJ] = storage[nmiI];
shop[nmiJ] -= storage[nmiI];
sum += mas[nmiI][nmiJ] * emptyMas[nmiI][nmiJ];
I[nmiI] = true;
}
}
}
free(storage);
free(shop);
free(I);
free(J);
return sum;
}
void PartI(){
const int n = 3;
const int m = 4;
int *storage, *shop, **Emas, **mas;
storage = (int*)malloc(n*sizeof(int));
shop = (int*)malloc(m*sizeof(int));
Emas = (int**)malloc(n*sizeof(int*));
mas = (int**)malloc(n*sizeof(int*));
for(int i = 0; i < m; i++){
Emas[i] = (int*)calloc(m, sizeof(int));
mas[i] = (int*)calloc(m, sizeof(int));
}
storage[0] = 30;
storage[1] = 5;
storage[2] = 15;
shop[0] = 17;
shop[1] = 11;
shop[2] = 10;
shop[3] = 12;
mas[0][0] = 1;
mas[0][1] = 5;
mas[0][2] = 1;
mas[0][3] = 8;
mas[1][0] = 8;
mas[1][1] = 9;
mas[1][2] = 4;
mas[1][3] = 6;
mas[2][0] = 7;
mas[2][1] = 1;
mas[2][2] = 9;
mas[2][3] = 1;
show("\t\t\t\tТаблица маршрутов\n", mas, storage, shop, n, m);
int sum = NorthWest(storage, shop, m, n, Emas, mas);
show("Поиск начального приближения методом северо-западного угла:\n\t\t\t\tПлан маршрута\n", Emas, storage, shop, n, m);
std::cout << "Цена всей перевозки: " << sum << std::endl;
//Har(shop,storage, m, n, Emas, mas);
for ( int i = 0; i < n; i++){
for ( int j = 0; j < m; j++){
Emas[i][j] = 0;
}
}
sum = MinPrice(storage, shop, m, n, Emas, mas);
show("Поиск начального приближения методом минимальных стоимостей:\n\t\t\t\tПлан маршрута\n", Emas, storage, shop, n, m);
std::cout << "Цена всей перевозки: " << sum << std::endl;
//Har(shop,storage, m, n, Emas, mas);
for ( int i = 0; i < n; ++i){
free(Emas[i]);
free(mas[i]);
}
free(storage);
free(shop);
}
int main(){
setlocale(LC_ALL, "Russian");
PartI();
}