Từ 1 tới 5 trên tổng số 5 kết quả

Đề tài: Bài Toán cái Túi Sử dụng thuật toán sinh hoán vị

  1. #1
    Ngày gia nhập
    03 2012
    Bài viết
    1

    Mặc định Bài Toán cái Túi Sử dụng thuật toán sinh hoán vị

    Đề Bài

    Một người du lịch cần đi qua N thành phố N<=100. Xuất phát từ thành phố 1 người du lịch muốn đi qua tất cả các thành phố còn lại mỗi thành phố đúng 1 lần rồi trở về thành phố ban đầu . Biết chi phí đi từ thành phố thứ i đến thành phố thứ j là C(ij). Hãy viết chương trình có chi phí tối đa cho người du lịch

    Chiphi.in

    6
    10 64 57 29 18 15
    34 20 19 71 16 12
    57 49 40 16 11 19
    29 21 46 26 21 18
    28 16 11 21 21 37
    15 12 15 48 37 30

    cucdai.out

    82

    1 2 6 3 54 1

    C Code:
    1. #include <stdio.h>
    2. #include <conio.h>
    3.  
    4. int T[100][100], X[100], N, OK = 1, Max = -32000, MaxX[100], xp = 1;
    5. FILE *fp;
    6.  
    7. void Read_Data(void) {
    8.     int i, j;
    9.     fp = fopen("d:\\test3_bai12.txt", "r");
    10.     fscanf(fp, "%d", &N);
    11.     for (i = 1; i <= N; i++) {
    12.         X[i] = i;
    13.     }
    14.     for (i = 1; i <= N; i++)
    15.         for (j = 1; j <= N; j++)
    16.             fscanf(fp, "%d", &T[i][j]);
    17.     fclose(fp);
    18. }
    19.  
    20. void Result(void) {
    21.     int i;
    22.     printf("\n");
    23.     fprintf(fp, "%s", "\n");
    24.     for (i = 1; i <= N; i++) {
    25.         printf("%3d", MaxX[i]);
    26.         fprintf(fp, "%3d", MaxX[i]);
    27.     }
    28.     printf("%3s", "1");
    29.     fprintf(fp, "%3s", "1");
    30. }
    31.  
    32. void Next_Permutation(void) {
    33.     int j = N - 1, k, t, r, S;
    34.     while(j > 0 && X[j] > X[j + 1]) j--;
    35.     if (j > 0) {
    36.         k = N;
    37.         while(X[j] > X[k]) k--;
    38.         t = X[j]; X[j] = X[k]; X[k] = t;
    39.         r = j + 1, S = N;
    40.         while(r <= S) {
    41.             t = X[r]; X[r] = X[S]; X[S] = t;
    42.             r++;S--;
    43.         }
    44.     }
    45.     else OK = 0;
    46. }
    47.  
    48. void Test(void) {
    49.     int i, S = 0;
    50.     if (xp == X[1]) {
    51.         for (i = 1; i <= N; i++) {
    52.             S = S + T[X[i]][X[i + 1]];
    53.         }
    54.         S = S + T[X[N]][xp];
    55.         if (S > Max) {
    56.             Max = S;
    57.             for (i = 1; i <= N; i++) {
    58.                 MaxX[i] = X[i];
    59.             }
    60.         }
    61.     }
    62. }
    63.  
    64. void main(void) {
    65.     Read_Data();
    66.     while(OK) {
    67.         Test();
    68.         Next_Permutation();
    69.     }
    70.     fp = fopen("d:\\cucdai.txt", "w");
    71.     fprintf(fp, "%3d", Max);
    72.     printf("\n Max = %d", Max);
    73.     Result();
    74.     fclose(fp);
    75.     getch();
    76.     return;
    77. }


    Mọi người thử góp ý xem đoạn code trên đã đúng chưa. Mình chạy thử với dữ liệu như Chiphi.in như trên thấy kết quả là

    238
    1 6 5 2 4 3 1

  2. #2
    Ngày gia nhập
    03 2012
    Bài viết
    1

    Các bác hay phác họa cấu trúc giải thuật hộ em về bài toán cái túi đc ko

    các bác trên diễn đàn ai có tài liệu c cơ bản cho người học cho em xin với em cám ơn các bác nhiều!
    Đã được chỉnh sửa lần cuối bởi aydada : 18-03-2012 lúc 06:19 PM. Lý do: làm liền các bài viết

  3. #3
    Ngày gia nhập
    03 2011
    Bài viết
    12

    Trích dẫn Nguyên bản được gửi bởi LOIHH Xem bài viết
    Các bác hay phác họa cấu trúc giải thuật hộ em về bài toán cái túi đc ko
    cậu có thể dùng thuật toán nhánh cận ...

  4. #4
    Ngày gia nhập
    07 2010
    Bài viết
    3

    mình dùng hoán vị:

    C Code:
    1. #include <iostream>
    2. #include <algorithm>
    3. using namespace std;
    4.  
    5. main(){
    6.     int n,mt[100][100],hv[100],cv[100];
    7.     long tong,kq=LONG_MAX;
    8.     cin>>n;
    9.     for(int i=1;i<=n;i++)
    10.     {
    11.         for(int j=1;j<=n;j++)
    12.         cin>>mt[i][j];
    13.         hv[i]=i;
    14.     }
    15.     do{
    16.         tong =0;
    17.         for(int i=1;i<=n;i++){
    18.             tong += mt[hv[i]][i];
    19.         }
    20.         if(tong<kq) {
    21.             kq=min(kq,tong);
    22.             for(int z=1;z<=n;z++)
    23.             cv[z]=hv[z];
    24.         }
    25.     }
    26.     while(next_permutation(hv+1,hv+n+1));
    27.     cout<<kq<<endl;
    28.     for(int i=1;i<=n;i++)
    29.     cout<<cv[i]<<" ";
    30.    
    31.    
    32.  
    33. }

  5. #5
    Ngày gia nhập
    07 2010
    Bài viết
    3

    Chiphi.in

    6
    10 64 57 29 18 15
    34 20 19 71 16 12
    57 49 40 16 11 19
    29 21 46 26 21 18
    28 16 11 21 21 37
    15 12 15 48 37 30

    cucdai.out

    82

    1 2 6 3 54 1

    cái output này là đề bài cực tiểu chứ ko fai cực đại. code trên mình gửi là cực tiểu.zz

Các đề tài tương tự

  1. Cơ sở may túi vải, túi vải không dệt, túi môi trường, túi vải làm quà tặng, in logo lên túi vải
    Gửi bởi tranngocson186 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 18-05-2013, 01:47 PM
  2. Túi vải không dệt, túi vải bò, túi vải quảng cáo hội nghị rẻ đẹp
    Gửi bởi quynhcute trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 26-09-2012, 12:19 AM
  3. Combo túi chống sốc, dụng cụ vệ sinh, tấm dán silicon giá cực sốc
    Gửi bởi MaLongNo2 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 16-03-2012, 11:39 PM
  4. Túi xách,túi xách hàng hiệu,túi hiệu louis Vuitton,HerMes,Gucci,chanel hàng fake 1
    Gửi bởi dientuthaithang trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 06-02-2012, 10:09 AM
  5. Algorithm Thuật toán di truyền với bài toán cái túi 2
    Gửi bởi luannguyenit trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 0
    Bài viết cuối: 13-07-2011, 11:26 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn