Chatbox

Các bạn vui lòng dùng từ ngữ lịch sự và có văn hóa,sử dụng Tiếng Việt có dấu chuẩn. Chúc các bạn vui vẻ!
20/10/2013 23:10 # 1
vnttqb
Cấp độ: 13 - Kỹ năng: 8

Kinh nghiệm: 5/130 (4%)
Kĩ năng: 39/80 (49%)
Ngày gia nhập: 21/03/2011
Bài gởi: 785
Được cảm ơn: 319
[OLP Tin 2013] - Bài Toán Cái Túi


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();
}


======================================================================================================

Cuộc đời là một dòng sông. Ai không bơi thì chết. 
 

Name: Tien (Tory) TRAN
Email: TranTien29@gmail.com


 
Copyright© Đại học Duy Tân 2010 - 2019