PTTKTT - BÀI TOÁN BALO1 DÙNG THUẬT TOÁN QUY HOẠCH ĐỘNG

//BÀI TOÁN BALO1 DÙNG THUẬT TOÁN QUY HOẠCH ĐỘNG  


//Các bạn tự file dữ liệu có tên QHD_CaiBalo.inp

#include<stdio.h>

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

typedef struct{
	char TenDV[30];
	int TL,GT,PA;
}DoVat;
typedef int bang[50][100];

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

void InDS(DoVat *dsdv, int n, int W){
	int i, TongGT=0, TongTL=0;
	printf("|---|------------------|-----------|-----------|----------|\n");
	printf("|STT|    Ten Do Vat    |Trong Luong|  Gia Tri  |   P.An   |\n");
	printf("|---|------------------|-----------|-----------|----------|\n");
	for(i=0;i<n;i++){
		printf("|%2d |%-18s|%5d      |%5d      |%5d     |\n",
		(i+1),dsdv[i].TenDV,dsdv[i].TL,dsdv[i].GT,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= %-9d\n", W);
	printf(" Tong Trong luong    = %-9d\n", TongTL);
	printf(" Tong Gia tri        = %-9d\n", TongGT);
}

void TaoBang(DoVat *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]=V/dsdv[0].TL;
		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= V/dsdv[k].TL;
	   	  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 In(int n, int W, bang F, bang X){
	int V,k;
	for(k=0;k<n;k++){
	   for(V=0;V<=W;V++)
	       printf("|%4d%2d",F[k][V], X[k][V]);
	    printf("\n");
    }
}
void TraBang(DoVat *dsdv,int n, int W, bang F, bang X){
	int V,k;
	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;
	DoVat *dsdv;
	
	dsdv=ReadFromFile(&W,&n);
	
	TaoBang(dsdv,n,W,F,X);
	In(n,W,F,X);
	printf("\n");
	TraBang(dsdv,n,W,F,X);
	InDS(dsdv,n,W);
	
	free(dsdv);
	return 0;
}