Bài toán cái túi. Mấy đứa xem lại thử code thế ok chưa. đọc tham khảo thử nhé.
Có gì không hiểu cứ comment lại nhé
#include "stdio.h"
#include "conio.h"
int A[100][2];
int n,M;
void docfile()
{
FILE *f;
f=fopen("bai6.txt","rt");
fscanf(f,"%d%d",&n,&M); // so do vat va tong trong luong toi da cua tui
for( int i=1;i<=n;i++)
{
int giatri,khoiluong;
fscanf(f,"%d%d",&khoiluong,&giatri);
A[i][1]=khoiluong;
A[i][2]=giatri;
}
printf("\n CO %d do vat va trong luong toi da cua tui la %d\n",n,M);
for( int i=1;i<=n;i++)
printf("\n Vat thu %d co KL = %d va GT =%d",i,A[i][1],A[i][2]);
fclose(f);
}
int max(int a,int b) { if( a>b ) return a; else return b; }
int dequy(int ni,int m)
{
if( ni==0 ) return 0;
else
if( A[ni][1] > m )
return dequy(ni-1,m);
else
return max(dequy(ni-1,m),dequy(ni-1,m-A[ni][1])+A[ni][2] );
}
void F()
{
int F[100][100];
for (int i=0;i<=M;i++)
F[0][i]=0;
for ( int i=1;i<=n;i++)
for ( int j=0;j<=M;j++)
{
if( A[i][1] > j) F[i][j]=F[i-1][j];
else
F[i][j]= max(F[i-1][j],F[i-1][j-A[i][1]]+ A[i][2]);
}
printf("\n\nPHUONG PHAP QHD: GIA TRI LON NHAT CUA TUI LA: %d",F[n][M]);
printf("\n\n\n BANG PHUONG AN: GIA TRI CUA CAC BAI TOAN CON");
for ( int i=1;i<=n;i++)
{printf("\n\n");
for ( int j=0;j<=M;j++)
printf("%d ",F[i][j]);
}
}
int main()
{
docfile();
printf("\n\nPHUONG PHAP DE QUY: GIA TRI LON NHAT CUA TUI LA: %d ",dequy(n,M));
F();
getch();
}