BÀI TOÁN CÁI BA LÔ 3 DÙNG THUẬT TOÁN QUY

//BÀI TOÁN CÁI BA LÔ 3 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[20];
	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 InDanhSach(dovat *dsdv,int W,int n){
	int i, TongGT=0, TongTL=0;
	printf("|---|------------------|----------|----------|----------|\n");
	printf("|STT|    Ten Do Vat    |    TL    |    GT    |    PA    |\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= %-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 taobang(dovat *dsdv,int W,int n, 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,1);
		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,1);
	   	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 inbang(int W,int n, 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(dovat *dsdv,int W,int n, 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 W,n;
	bang F, X;
	dovat *dsdv;
	dsdv= ReadFromFile(&W, &n);
	
	taobang(dsdv,W,n,F,X);
	inbang(W,n,F,X);
	printf("\n");
	
	trabang(dsdv,W,n,F,X);
	InDanhSach(dsdv, W, n);
	free(dsdv);
	return 0;
}