PTTKTT - BÀI TOÁN CÁI BA LÔ 2 DÙNG THUẬT TOÁN QUY HOẠCH ĐỘNG

//BÀI TOÁN CÁI BA LÔ 2 DÙNG THUẬT TOÁN QUY HOẠCH ĐỘNG


//Các bạn tự tạo file dữ liệu 

#include<stdio.h>

#include<string.h>
#include<malloc.h>

typedef struct{
	char TenDV[30];
	int TL,GT,PA,SL;
}DoVat2;

typedef int bang[50][100];

DoVat2* ReadFromFile( int *W, int *n){
	FILE *f;
	f=fopen("QHD_CaiBalo2.inp","r");
	fscanf(f,"%d",W);
	DoVat2 *dsdv;
	dsdv=(DoVat2*)malloc(sizeof(DoVat2));
	int i=0;
	while(!feof(f)){
		fscanf(f,"%d%d%d%[^\n]", &dsdv[i].TL,&dsdv[i].GT,&dsdv[i].SL,&dsdv[i].TenDV);
		dsdv[i].PA=0;
		i++;
		dsdv=(DoVat2*)realloc(dsdv,sizeof(DoVat2)*(i+1));
	}
	*n=i;
	fclose(f);
	return dsdv;
}

void InDs(DoVat2 *dsdv,int W,int n){
	int i, TongGT=0, TongTL=0;
	printf("|---|------------------|----------|----------|----------|----------|\n");
	printf("|STT|    Ten Do Vat    |    TL    |    GT    |    SL    |    PA    |\n");
	printf("|---|------------------|----------|----------|----------|----------|\n");
	for(i=0;i<n;i++){
		printf("|%2d |%-18s|%5d     |%5d     |%5d     |%5d     |\n",
		(i+1),dsdv[i].TenDV,dsdv[i].TL,dsdv[i].GT,dsdv[i].SL,dsdv[i].PA);
		TongGT= TongGT +dsdv[i].PA*dsdv[i].GT;
		TongTL= TongTL +dsdv[i].PA*dsdv[i].TL;
	}
	printf("|---|------------------|----------|----------|----------|----------|\n");
	printf("Trong luong cua balo= %-5d\n",W);
	printf("Tong gia tri        = %-5d\n",TongGT);
	printf("Tong trong luong    = %-5d\n",TongTL);
}
int min(int a, int b){
	return a<b? a:b;
}
void TaoBang2(DoVat2 *dsdv, int n, int W, bang F, bang X){
	int xk,yk,k;
	int Fmax,Xmax,V;
	for(V=0;V<=W;V++){
		X[0][V]= min(V/dsdv[0].TL, dsdv[0].SL);
		F[0][V]= X[0][V]*dsdv[0].GT;
	}
	
	for(k=1;k<=n;k++)
	   for(V=0;V<=W;V++){
	   	  Fmax=F[k-1][V];
	   	  Xmax=0;
	   	  yk=min(V/dsdv[k].TL,dsdv[k].SL);
	   	  for(xk=0;xk<=yk;xk++)
	   	  	if( F[k-1][V-xk*dsdv[k].TL]+ xk*dsdv[k].GT > Fmax){
	   	  		Fmax=F[k-1][V-xk*dsdv[k].TL]+ xk*dsdv[k].GT;
	   	  		Xmax=xk;
				}
			F[k][V]=Fmax;
			X[k][V]=Xmax;	
	   	  
	   }
}

void InBang2( int n, int W, bang F, bang X){
	int k,V;
	for(k=1;k<=n;k++){
	   for(V=0;V<=W;V++)
	   	  printf("|%4d%2d", F[k][V], X[k][V]);
	    printf("\n");	  
    }
}

void Trabang(DoVat2 *dsdv, int n, int W, bang F, bang X){
	int k, V;
	V=W;
	for(k=n-1;k>=0;k--){
		dsdv[k].PA= X[k][V];
		V= V - X[k][V]*dsdv[k].TL;
	}
}
int main(){
	int n,W;
	bang F,X;
	DoVat2 * dsdv;
	dsdv= ReadFromFile(&W,&n);
	
	TaoBang2(dsdv,n,W,F,X);
	InBang2(n,W,F,X);
	printf("\n");
	Trabang(dsdv,n,W,F,X);
	InDs(dsdv,W,n);
	
	free(dsdv);
	return 0;
}