Đánh giá, nhận xét, review các công ty tuyển dụng
Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 14 kết quả

Đề tài: Thuật toán của bài toán cái túi và người du lịch

  1. #1
    No Avatar
    meohoang8x Khách

    Mặc định Thuật toán của bài toán cái túi và người du lịch

    Xin các bác cho em biết về thuật toán của bài toán cái túi và người du lịch, em ko hiểu gì về hai bài này cả.

  2. #2
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,918

    thuật toán là thuật toán nào ? 2 bài này có nhiều cách giải lắm hix hix ! hỏi thế sao mình biết được !

  3. #3
    Ngày gia nhập
    09 2007
    Bài viết
    17

    chậc mấy bài toán này hay lém, đọc bài này nhớ lão hdkinhcan quá , he he sao ko thấy lão vào thảo luận mấy bài này nữa nhỉ ?

  4. #4
    Ngày gia nhập
    11 2006
    Bài viết
    633

    Đây ko phải là thuật toán mà chỉ có thể gọi nó là thuật giải mà thôi, tên của bài toán chính xác là knapsack, các bạn có thể search google để tìm hiểu (nếu biết đọc tiếng Anh). Đây là 1 bài toán nằm trong các bài toán về Quy hoạch động

  5. #5
    Ngày gia nhập
    11 2007
    Bài viết
    9

    bạn nào có code viết trên C không vậy ? cho mình tham khảo với ^^
    code bài cái túi ai xem giúp mình cái,mình chạy nó k đc như ý muốn,khó hiểu lắm í
    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<stdlib.h>
    #include<math.h>
    #include<dos.h>
    #define TRUE 1
    #define FALSE 0
    #define MAX 100
    int x[MAX],xopt[MAX];
    float fopt,cost,weight;
    void Init(float *C,float *A,int *n,float *w)
    { int i;
    FILE *fp;
    fopt=0;weight=0;
    fp=fopen("caitui.in","r");
    if(fp==NULL)
    { printf("\nKhong co tep input");
    delay(5000);return;
    }
    fscanf(fp,"%d%f",n,w);
    for(i=1;i<=*n;i++) xopt[i]=0;
    printf("\nSo luong do vat%d:",*n);
    printf("\nGioi han tui %8.2f:",*w);
    printf("\nVector gia tri:");
    for(i=1;i<=*n;i++)
    {
    fscanf(fp,"%f",&C[i]);
    printf("%8.2f",A[i]);
    }
    printf("\nVEctor trong luong:");
    for(i=1;i<=*n;i++)
    { fscanf(fp,"%f",&A[i]);
    printf("%8.2f",A[i]);
    }
    fclose(fp);
    
    }
    void swap(int n)
    {
    int i;
    for(i=1;i<=n;i++)
    xopt[i]=x[i];
    }
    void Update_Kyluc(int n)
    {
    if(cost>fopt)
    {
    swap(n);
    fopt=cost;
    }
    }
    void Try(float *A,float *C,int n,float w,int i)
    {
    int j,t=(w-weight)/A[i];
    for(j=t;j>=0;j--)
    {
    x[i]=j;
    cost=cost+C[i]*x[i];
    weight=weight+x[i]*A[i];
    if(i==n)
    Update_Kyluc(n);
    else if(cost+C[i+1]*(w-weight)/A[i+1]>fopt)
    {
    Try(A,C,n,w,i+1);
    }
    weight=weight-A[i]*x[i];
    cost=cost-C[i]*x[i];
    }
    }
    void Result(int n)
    { int i;
    printf("\nGia tri do vat %8.2f",fopt);
    printf("\nPhuong an toi uu:");
    for(i=1;i<=n;i++)
    printf("%3d",xopt[i]);
    }
    void main(void)
    { int n;
    float A[MAX],C[MAX],w;
    clrscr();
    Init(C,A,&n,&w);
    Try(C,A,n,w,1);
    Result(n);
    getch();
    }

  6. #6
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,918

    Mặc định Thuật toán của bài toán cái túi và người du lịch

    Bài này thực ra có 2 phiên bản :
    - Phiên bản 1 : là số đồ chọn là số nguyên.
    ví dụ :
    có 3 món đồ với dung lượng túi là 10
    + món 1 : nặng 4 , giá trị 10
    + món 2 : nặng 6 , giá trị 10
    + món 3 : nặng 10, giá trị 21
    Vì giá trị nguyên, nên dễ thấy ta phải chọn món thứ 3 để có giá trị là lớn nhất
    - Phiên bản 2 : là tên trộm có thể cắt món đồ ra để được giá trị lớn nhất , cũng với ví dụ trên ta có giá trị 1 phần của từng món như sau :
    10 / 4 = 2.5
    10 / 6 = 1.666667
    21 / 10 = 2.1
    Tức là nếu theo cách này thì ta sẽ chọn món thứ nhất 4kg + 6kg ( của món thứ 3 ) thì sẽ được giá trị lớn nhất.
    Code của bạn mình nghĩ là giải theo phương pháp tham lam nhưng cách đặt tên biến i,j.. nên đọc vào mệt lắm. Code này mình viết theo 2 phương pháp, mình giải phiên bản 1 bằng quy hoạch động và phiên bản 2 bằng tham lam :
    -Giải thuật cho phương pháp tham lam rất đơn giản : sắp xếp lại các tỉ số giá trị ( cái mình vừa ví dụ ) sau đó thử sai là xong .
    -Giải thuật cho QHD cũng đơn giản như sau :
    F[i][j] là giá trị lớn nhất có thể đạt được bao gồm i món đồ và giới hạn trọng lượng là j
    thì ta có :
    Không lấy món đồ đó thì thứ i thì : F[i][j] = F[i-1][j]
    Ngược lại nếu chọn món đồ thứ i + điều kiện [được giá trị lớn hơn] thì
    F[i][j] = F[i-1][j-khối lượng[i]] + giá trị[i]
    Ta chỉ cần tính cho tới F[món đồ][giá tiền] nhập vào là xong
    Đây là code , có chỗ nào không hiểu thì mình sẽ giải thích :
    C++ Code:
    1. #include <iostream>
    2. #include <iomanip>
    3. #include <fstream>
    4. #include <algorithm> //sort function
    5.  
    6. using namespace std;
    7.  
    8.  
    9. class Knapstack
    10. {
    11.     public :
    12.        
    13.         Knapstack(int number_of_items, int weight_of_bag);
    14.        ~Knapstack();
    15.    
    16.         //Copy constructor
    17.         Knapstack::Knapstack(Knapstack &copy_object);
    18.         //overloading operator "="
    19.         const Knapstack &operator = (Knapstack &);
    20.        
    21.         /*method for greedy*/
    22.         void Solving_by_greedy();
    23.         void Sort_items();
    24.      
    25.         /*method for dynamic programming*/
    26.         void Solving_by_dynamic_programming();
    27.         void Dynamic_programming_trace_solution();
    28.        
    29.         friend istream &operator >> (istream &, Knapstack &);
    30.        
    31.     private :
    32.        
    33.         int weight_of_bag;
    34.         int number_of_items;
    35.        
    36.        //data information
    37.         int *items_No;
    38.         int *items_value;
    39.         int *items_weight;
    40.         //solution array
    41.         float *greedy_solution;
    42.         int **dynamic_solution;
    43. };
    44.  
    45.  
    46. Knapstack::Knapstack(int number_of_items, int weight_of_bag)
    47.     :number_of_items(number_of_items), weight_of_bag(weight_of_bag)
    48. {
    49.     greedy_solution = new float[number_of_items+1];
    50.     items_No = new int[number_of_items+1];
    51.     items_value = new int[number_of_items+1];
    52.     items_weight = new int[number_of_items+1];
    53.            
    54.            
    55.     dynamic_solution = new int *[number_of_items+1];
    56.     for(int x = 0; x <= number_of_items; x++)
    57.     {
    58.         dynamic_solution[x] = new int[weight_of_bag+1];
    59.     }
    60.              
    61.     for(int x = 0; x <= number_of_items; x++)
    62.     {
    63.         *(items_No + x) = x;
    64.         *(items_value + x) = 0;
    65.         *(items_weight + x) = 0;
    66.         *(greedy_solution + x) = 0.0;
    67.     }
    68.              
    69.     for(int x = 0; x <= number_of_items; x++){
    70.         for(int y = 0; y <= weight_of_bag; y++){
    71.             dynamic_solution[x][y] = 0;
    72.         }
    73.     }
    74. }
    75.  
    76.  
    77. //Destructor
    78.  Knapstack::~Knapstack()
    79. {
    80.     delete[] items_No;
    81.     delete[] items_value;
    82.     delete[] items_weight;
    83.        
    84.     delete[] greedy_solution;
    85.     for(int x = 0; x <= number_of_items; x++){
    86.         delete[] dynamic_solution[x];
    87.     }
    88.     delete[] dynamic_solution;
    89. }
    90.  
    91.  
    92. //Copy constructor
    93. Knapstack::Knapstack(Knapstack &copy_object)
    94.     :number_of_items(copy_object.number_of_items), weight_of_bag(copy_object.weight_of_bag)
    95. {
    96.     //For array of greedy algorithm
    97.     greedy_solution = new float[number_of_items+1];
    98.     items_No = new int[number_of_items+1];
    99.     items_value = new int[number_of_items+1];
    100.     items_weight = new int[number_of_items+1];
    101.  
    102.     for(int x = 0; x <= number_of_items; x++)
    103.     {
    104.         *(items_No + x) = copy_object.items_No[x];
    105.         *(items_value + x) = copy_object.items_value[x];
    106.         *(items_weight + x) = copy_object.items_weight[x];
    107.         *(greedy_solution + x) = copy_object.greedy_solution[x];
    108.     }
    109.            
    110.     //For array of dynamic programming algorithm
    111.     dynamic_solution = new int *[number_of_items+1];
    112.     for(int x = 0; x <= number_of_items; x++)
    113.     {
    114.         dynamic_solution[x] = new int[weight_of_bag+1];
    115.     }
    116.    
    117.     for (int x = 0; x <= number_of_items; x++)
    118.     {
    119.         for (int y = 0; y <= weight_of_bag; y++)
    120.         {
    121.             dynamic_solution[x][y] = copy_object.dynamic_solution[x][y];
    122.         }
    123.     }
    124. }
    125.  
    126.  
    127. const Knapstack &Knapstack::operator = (Knapstack &obj)
    128. {
    129.     if (&obj != this) //check for self-assignment
    130.     {
    131.         //deallocate new left-side of array
    132.         if((number_of_items != obj.number_of_items) || (weight_of_bag != obj.weight_of_bag))
    133.         {
    134.             //Reclaim space
    135.             delete[] items_No;
    136.             delete[] items_value;
    137.             delete[] items_weight;
    138.             delete[] greedy_solution;
    139.              
    140.             for( int x = 0; x <= number_of_items; x++){
    141.                 delete[] dynamic_solution[x];
    142.             }
    143.             delete[] dynamic_solution;
    144.             /*----END RECLAIM SPACE----*/
    145.            
    146.             //Resize object.
    147.             number_of_items = obj.number_of_items;
    148.             weight_of_bag = obj.weight_of_bag;
    149.            
    150.             //Create space for array copy
    151.             dynamic_solution = new int*[number_of_items+1];
    152.             for(int x = 0; x <= number_of_items; x++)
    153.             {
    154.                 dynamic_solution[x] = new int[weight_of_bag+1];
    155.             }
    156.          
    157.        
    158.             items_No = new int[number_of_items+1];
    159.             items_value = new int[number_of_items+1];
    160.             items_weight = new int[number_of_items+1];
    161.             greedy_solution = new float[number_of_items+1];
    162.             /*----END CREATE SPACE----*/
    163.          
    164.             //copy all arrays into object
    165.             for(int x = 0; x <= number_of_items; x++)
    166.             {
    167.                 *(items_No + x) = obj.items_No[x];
    168.                 *(items_value + x) = obj.items_value[x];
    169.                 *(items_weight + x) = obj.items_weight[x];
    170.                 *(greedy_solution + x) = obj.greedy_solution[x];
    171.             }
    172.          
    173.             for (int x = 0; x <= number_of_items; x++)
    174.             {
    175.                 for (int y = 0; y <= weight_of_bag; y++)    
    176.                 {
    177.                     dynamic_solution[x][y] = obj.dynamic_solution[x][y];
    178.                 }
    179.             }
    180.         }
    181.     }
    182.     return *this; //reference return
    183. }  
    184.    
    185.  
    186. istream &operator >> (istream &input, Knapstack &obj)
    187. {
    188.     cout << "\n### Data Information      ###\n";
    189.     cout << "\nThe number of items : ";
    190.     input >> obj.number_of_items;
    191.     cout << "\nThe maximum capacity of bags: ";
    192.     input >> obj.weight_of_bag;
    193.  
    194.     for(int i = 1; i <= obj.number_of_items; i++)
    195.     {
    196.         cout << " The  [" << i << "] item weigh : ";
    197.         input >> obj.items_weight[i];
    198.         cout << " Its value is  :  ";
    199.         input >> obj.items_value[i];
    200.         cout << endl;
    201.     }
    202.  
    203.     return input;
    204. }
    205.  
    206.  
    207. void Knapstack::Sort_items()
    208. {
    209.    for(int x = number_of_items; x >= 2; x--)
    210.     {
    211.         for(int y = 1; y <= number_of_items - x; y++)
    212.         {
    213.             if(((float)items_value[y]/items_weight[y]) > ((float)items_value[y-1]/items_weight[y-1]))
    214.             {
    215.                 swap(items_weight[y], items_weight[y-1]);
    216.                 swap(items_value[y], items_value[y-1]);
    217.                 swap(items_No[y], items_No[y-1]);
    218.             }
    219.         }
    220.     }
    221. }
    222.  
    223.  
    224. void Knapstack::Solving_by_greedy()
    225. {
    226.     int _the;//the item
    227.     float max_profit = 0.0;
    228.  
    229.     Sort_items();
    230.    
    231.     for(_the = 1; _the < number_of_items; _the++)
    232.     {
    233.         if(items_weight[_the] > weight_of_bag)
    234.             break;
    235.        
    236.         greedy_solution[_the] = 1.0;
    237.              
    238.         weight_of_bag = weight_of_bag - items_weight[_the];
    239.         max_profit += items_value[_the];
    240.              
    241.         cout << "\n Items chosen : "<< items_No[_the]
    242.              << "\nwith the % quantiy %:" << greedy_solution[_the] << endl;
    243.                  
    244.     }
    245.    
    246.    
    247.     if(_the <= number_of_items)
    248.     {              
    249.         greedy_solution[_the] = (float)weight_of_bag/items_weight[_the];
    250.         cout << "\n" << items_No[_the] << "\nwith the quantiy % chosen : " << greedy_solution[_the] << endl;
    251.         max_profit = max_profit + (greedy_solution[_the]*items_value[_the]);
    252.     }
    253.     cout << "\n Maximum value the thief can get : " << max_profit;
    254. }
    255.  
    256.  
    257. void Knapstack::Solving_by_dynamic_programming()
    258. {
    259.     for (int x = 1; x <= number_of_items; x++)
    260.     {
    261.         for (int y = 0; y <= weight_of_bag; y++)
    262.         {
    263.             dynamic_solution[x][y] = dynamic_solution[x-1][y];
    264.             if (y >= items_weight[x] && dynamic_solution[x][y] < dynamic_solution[x-1][y-items_weight[x]] + items_value[x] && (y-items_weight[x]) >= 0)
    265.             {
    266.                 dynamic_solution[x][y] = dynamic_solution[x-1][y-items_weight[x]] + items_value[x];
    267.             }
    268.         }
    269.     }
    270. }
    271.  
    272. void Knapstack::Dynamic_programming_trace_solution()
    273. {
    274.     cout << "Maximum value the thief can get : "
    275.          << dynamic_solution[number_of_items][weight_of_bag] << endl;
    276.      
    277.     while (number_of_items != 0)
    278.     {
    279.         if(dynamic_solution[number_of_items][weight_of_bag] != dynamic_solution[number_of_items-1][weight_of_bag])
    280.         {
    281.             cout << "Chosen items are : " << number_of_items;
    282.             weight_of_bag = weight_of_bag - items_weight[number_of_items];
    283.         }
    284.         number_of_items--;
    285.     }
    286. }
    287.  
    288. void Menu()
    289. {
    290.     Knapstack problem(10,10);
    291.     cin >> problem;
    292.    
    293.     int command;
    294.     cout << "Enter a method for solving knapstack problems :\n\n"
    295.          << "\n[1].Greedy\n"
    296.          << "\n[2].Dynamic programming\n" << endl;
    297.     cin >> command;
    298.    
    299.    
    300.     if (command == 1)
    301.     {
    302.         problem.Solving_by_greedy();
    303.     }
    304.     else
    305.     {
    306.         problem.Solving_by_dynamic_programming();
    307.         problem.Dynamic_programming_trace_solution();
    308.     }
    309. }
    310.  
    311. int main()
    312. {
    313.     Menu();
    314.     system("pause");
    315.     return 0;
    316. }
    Đã được chỉnh sửa lần cuối bởi rox_rook : 02-03-2008 lúc 05:17 AM.

  7. #7
    Ngày gia nhập
    11 2007
    Bài viết
    9

    lúc mình chạy í,nhập y như ví dụ của bạn,đến khi chọn 1,greedy thì k chạy đc,chọn dynamic thì ok...thanks bạn nhiều nha ^^

  8. #8
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,918

    Hic, sorry bạn nha ! Do lúc đầu bug tại thằng dynamic, chăm chú vào nó mà quên khởi tạo cho mãng Items_No[]. Bạn sữa lại ở constructor :
    PHP Code:
    for(int x 0<= number_of_itemsx++)
        {
            *(
    items_No x) = x+1;//fixed
            
    *(items_value x) = 0;
            *(
    items_weight x) = 0;
            *(
    greedy_solution x) = 0.0;
        } [/
    quote

  9. #9
    Ngày gia nhập
    11 2007
    Bài viết
    9

    bạn ơi bạn tách riêng cho mình chỉ có quy hoạch động đc k ?
    thanks bạn nhiều lắm í ^^

  10. #10
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,918

    Giải thuật mình đã trình bày, code mình cũng chú thích ghi ra rõ ràng 2 phần, hơn nữa mình đặt tên biến và hàm hầu như phản ánh toàn nội dung của nó rồi còn gì ? Bạn không chịu đọc mà bắt mình code thì chắc chắn câu trả lời của mình sẽ là không !! Nếu bạn còn vướng mắt hoặc bạn code còn sai thì post lên đây mình sẽ giúp ! Còn code cho bạn chắc chắn mình không làm ! Thân !

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. Túi vải không dêt, làm túi vải không dệt tại hà nội, túi hội thảo
    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: 31-08-2012, 01:19 AM
  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. Bộ Sưu Tập Túi Thời Trang Cho Mùa Đông Của Shop Chuột Túi ( chuottui.eway.vn )
    Gửi bởi qhtattoo.com 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: 20-11-2011, 09:32 AM

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