/*
Programowanie dynamiczne: problem zaladunku
Program pobrano ze strony www.algorytm.org
Opracowal: Michal Knasiecki
Nalezy zapoznac sie z plikiem "!!!Format_danych.txt"

		********************************************
		*UWAGA: Dane sa wczytywane z pliku dane.txt*
		********************************************

*/
#include <conio>
#include <stdio>
#include <stdlib>
FILE 	*plik;
int 	n; 					//Liczba typów kontenerów Max=20
int 	b; 					//Ladownosc statku Max=30
//								Dla jasnosci kodu pomine zerowe indeksy w tablicach
int 	ciezar[21]; 		//Tablica ciezarów kontenerów
int 	pojemnosc[21]; 	//Tablica pojemnosci kontenerów
int 	rozwiazanie[21];	//Tablica z rozwiazaniem
int	x[21][31];			//Tablica pomocnicza o wymiarze n*b
int	f[21][31];			//Tablica pomocnicza o wymiarze n*b
//
void oblicz(void)
{
int l,j;
div_t q;
//
for (l=0;l<=b;l++)
	{
	q=div(l,ciezar[1]);
   f[1][l]=pojemnosc[1]*q.quot;
   if (f[1][l]==0) x[1][l]=0; else x[1][l]=1;
   }
for (j=2;j<=n;j++)
	{
   for (l=1;l<=b;l++)
   	{              	//Uroczy wzorek:
      if (l-ciezar[j]<0) f[j][l]=f[j-1][l]; else
   		if (f[j-1][l]>f[j][l-ciezar[j]]+pojemnosc[j]) f[j][l]=f[j-1][l];
         	else f[j][l]=f[j][l-ciezar[j]]+pojemnosc[j];
         if (l-ciezar[j]<0) x[j][l]=x[j-1][l];
         	else if (f[j-1][l]>f[j][l-ciezar[j]]+pojemnosc[j]) x[j][l]=x[j-1][l]; else
            	x[j][l]=j;
      }
   }
j=b;
do
	{
   rozwiazanie[x[n][j]]++;
   j=j-ciezar[x[n][j]];
   }
while ((j>0)&&(ciezar[x[n][j]]!=0));
//Wypisywanie rozwiazania:
printf("Roziwiazanie:\n");
for (j=1;j<=n;j++) printf("Typ: %i, Ilosc: %i\n",j,rozwiazanie[j]);
}
void main(void)
{
int i;
//
clrscr();
if ((plik=fopen("dane.txt","r"))==NULL)
	{
   printf("Plik \"dane.txt\" z danymi wejsciowymi nie istnieje\n");
   printf("Dowlony klawisz...");
   getch();
   } else
   { 															//Wczytywanie danych z pliku
   printf("Dane wejsciowe:\n");
   fscanf(plik,"%i",&n);
   printf("Liczba typow kontenerow: %i\n",n);
   fscanf(plik,"%i",&b);
   printf("Ladownosc statku: %i\n",b);
   for (i=0;i<n;i++)
   	{
   	fscanf(plik,"%i",&ciezar[i+1]);
   	printf("Ciezar konteneru #%i: %i\n",i+1,ciezar[i+1]);
      }
   for (i=0;i<n;i++)
   	{
   	fscanf(plik,"%i",&pojemnosc[i+1]);
   	printf("Pojemnosc konteneru #%i: %i\n",i+1,pojemnosc[i+1]);
      }
   fclose(plik);
   oblicz();
   getch();
   }
}