#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#define A_SIZE 3
#define B_SIZE 5
#define MAX_NUM 100
void PrintPlan(std::wstring message, int **X, int *A, int *B, int aSize, int bSize){
std::wcout << message;
for(int i = 0; i < bSize; i++){
printf("\tB[%i]", B[i]);
}
printf("\n");
for(int i = 0; i < aSize; i++){
printf("A[%i]:", A[i]);
for(int j = 0; j < bSize; j++){
printf("\t%i", X[i][j]);
}
printf("\n");
}
printf("\n");
}
void PrintPoint(std::wstring message, int *A, char point,int aSize){
std::wcout << message;
for(int i = 0; i < aSize; i++){
printf("%c[%i]: %i\n", point, i, A[i]);
}
printf("\n");
}
int NorthwestCornerMethod(int* A1, int aSize, int* B1, int bSize, int** X, int** C){
int *A = (int*)malloc(aSize*sizeof(int));
for(int i = 0; i < aSize; i++){
A[i] = A1[i];
}
int *B = (int*)malloc(bSize*sizeof(int));
for(int i = 0; i < bSize; i++){
B[i] = B1[i];
}
int aIndex = 0, bIndex = 0, sum = 0;
while(aIndex < aSize && bIndex < bSize){
if(A[aIndex] > B[bIndex]){
X[aIndex][bIndex] = B[bIndex];
A[aIndex] -= B[bIndex];
sum += C[aIndex][bIndex]*X[aIndex][bIndex];
bIndex++;
}
else{
X[aIndex][bIndex] = A[aIndex];
B[bIndex] -= A[aIndex];
sum += C[aIndex][bIndex]*X[aIndex][bIndex];
aIndex++;
}
}
free(A);
free(B);
return sum;
}
int MinimalPricesMethod(int* A1, int aSize, int* B1, int bSize, int** X, int** C){
int *A = (int*)malloc(aSize*sizeof(int));
for(int i = 0; i < aSize; i++){
A[i] = A1[i];
}
int *B = (int*)malloc(bSize*sizeof(int));
for(int i = 0; i < bSize; i++){
B[i] = B1[i];
}
int sum = 0, minI, minJ;
bool result = true;
bool *usedI = (bool*)calloc(aSize, sizeof(bool));
bool *usedJ = (bool*)calloc(bSize, sizeof(bool));
while(result){
result = false;
for(int i = 0; i < aSize; i++){
if(!usedI[i]){
minI = i;
break;
}
}
for(int i = 0; i < bSize; i++){
if(!usedJ[i]){
minJ = i;
break;
}
}
for(int i = 0; i < aSize; i++){
for(int j = 0; j < bSize; j++){
if(C[minI][minJ] >= C[i][j] && !usedI[i] && !usedJ[j]){
minI = i;
minJ = j;
result = true;
}
}
}
if(result){
if(A[minI] > B[minJ]){
X[minI][minJ] = B[minJ];
A[minI] -= B[minJ];
sum += C[minI][minJ]*X[minI][minJ];
usedJ[minJ] = true;
}
else{
X[minI][minJ] = A[minI];
B[minJ] -= A[minI];
sum += C[minI][minJ]*X[minI][minJ];
usedI[minI] = true;
}
}
}
free(A);
free(B);
free(usedI);
free(usedJ);
return sum;
}
void MakeRandomTask(int aSize, int bSize, int maxNum){
int *A, *B, **X, **C;
A = (int*)malloc(aSize*sizeof(int));
B = (int*)malloc(bSize*sizeof(int));
X = (int**)malloc(aSize*sizeof(int*));
C = (int**)malloc(aSize*sizeof(int*));
srand(time(NULL));
for(int i = 0; i < aSize; i++){
A[i] = rand()%maxNum;
X[i] = (int*)calloc(bSize, sizeof(int));
C[i] = (int*)calloc(bSize, sizeof(int));
for(int j = 0; j < bSize; j++){
if(!i){
B[j] = rand()%maxNum;
}
C[i][j] = rand()%maxNum;
}
}
//PrintPoint(L"Пункты отправления:\n", A, 'A', aSize);
//PrintPoint(L"Пункты назначения:\n", B, 'B', bSize);
PrintPlan(L"\t\tСтоимость перевозок\n", C, A, B, aSize, bSize);
int sum = NorthwestCornerMethod(A, aSize, B, bSize, X, C);
PrintPlan(L"Метод северо-западного угла:\n\t\tПлан перевозок\n", X, A, B, aSize, bSize);
std::wcout << L"Общий объем перевозок в тонно-километрах: " << sum << std::endl;
for(int i = 0; i < aSize; i++){
for(int j = 0; j < bSize; j++){
X[i][j] = 0;
}
}
sum = MinimalPricesMethod(A, aSize, B, bSize, X, C);
PrintPlan(L"\nМетод минимальных стоимостей:\n\t\tПлан перевозок\n", X, A, B, aSize, bSize);
std::wcout << L"Общий объем перевозок в тонно-километрах: " << sum << std::endl;
for(int i = 0; i < aSize; i++){
free(X[i]);
free(C[i]);
}
free(A);
free(B);
free(X);
free(C);
}
void MakeKnownTask(){
int *A, *B, **X, **C;
A = (int*)malloc(3*sizeof(int));
B = (int*)malloc(5*sizeof(int));
X = (int**)malloc(3*sizeof(int*));
C = (int**)malloc(3*sizeof(int*));
for(int i = 0; i < 3; i++){
X[i] = (int*)calloc(5, sizeof(int));
C[i] = (int*)calloc(5, sizeof(int));
}
A[0] = 300;
A[1] = 150;
A[2] = 250;
B[0] = 170;
B[1] = 110;
B[2] = 100;
B[3] = 120;
B[4] = 200;
C[0][0] = 70;
C[0][1] = 50;
C[0][2] = 15;
C[0][3] = 80;
C[0][4] = 70;
C[1][0] = 80;
C[1][1] = 90;
C[1][2] = 40;
C[1][3] = 60;
C[1][4] = 85;
C[2][0] = 50;
C[2][1] = 10;
C[2][2] = 90;
C[2][3] = 11;
C[2][4] = 25;
//PrintPoint(L"Пункты отправления:\n", A, 'A', 3);
//PrintPoint(L"Пункты назначения:\n", B, 'B', 5);
PrintPlan(L"\t\tСтоимость перевозок\n", C, A, B, 3, 5);
int sum = NorthwestCornerMethod(A, 3, B, 5, X, C);
PrintPlan(L"Метод северо-западного угла:\n\t\tПлан перевозок\n", X, A, B, 3, 5);
std::wcout << L"Общий объем перевозок в тонно-километрах: " << sum << std::endl;
for(int i = 0; i < 3; i++){
for(int j = 0; j < 5; j++){
X[i][j] = 0;
}
}
sum = MinimalPricesMethod(A, 3, B, 5, X, C);
PrintPlan(L"\nМетод минимальных стоимостей:\n\t\tПлан перевозок\n", X, A, B, 3, 5);
std::wcout << L"Общий объем перевозок в тонно-километрах: " << sum << std::endl;
for(int i = 0; i < 3; i++){
free(X[i]);
free(C[i]);
}
free(A);
free(B);
free(X);
free(C);
}
using namespace std;
int main()
{
setlocale(LC_ALL, ".866");
MakeKnownTask();
//MakeRandomTask(A_SIZE, B_SIZE, MAX_NUM);
return 0;
}