Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    Admin


    Quản trị viên
    Quản trị viên
    Code bài toán cái túi
    Đầu vào là một file .txt chứa các thông tin: số lượng đồ vật, khối lượng tối đa của túi, dãy các giá trị trọng lượng các đồ vật, dãy các giá trị sử dụng các đồ vật.
    Các số trong file cách nhau 1 dấu cách hoặc dấu xuống dòng.
    Ví dụ: số đồ vật là 4, khối lượng tối đa của túi là 30, trọng lượng các đồ vật là: 3,4,5,6; giá trị các đồ vật là 5,4,7,3; thì file đầu vào có thể viết như sau:
    Code:
    4 30
    3 4 5 6
    5 4 7 3
    Nguyên gốc code C#
    Code:
    #include <stdio.h>
    #include <conio.h>
    typedef int ai[50];
    typedef float af[50];
    af c,a;
    ai x, xopt, ind;
    int n;
    float w, fopt, cost, weight;
    FILE *input;
    void batdau()
    {
        int i,j,tg;
        float t;
        fopt=0; weight=0;
        FOR(i=1; i<=n; i++)
        {
            ind[i]=i;
            x[i]=0;
            xopt[i]=0;
        }
        FOR(i=1; i<=n-1; i++)
            FOR(j=1; j<=n; j++)
                if(c[i]/a[i]<c[j]/a[j])
                {
                    t=c[i]; c[i]=c[j]; c[j]=t;
                    t=a[i]; a[i]=a[j]; a[j]=t;
                    tg=ind[i]; ind[i]=ind[j]; ind[j]=tg;
                }
    }
    void nhapfile()
    {
        char inName[64];
        int i;
        printf("Enter input file name: ");
        scanf("%63s", inName);
        if ((input = fopen (inName, "r")) != NULL)
        {
        fscanf(input,"%d",&n); // so luong do vat
        fscanf(input,"%f",&w); // trong luong cai tui
        FOR(i=1; i<=n; i++) fscanf(input,"%f", &a[i]); // trong luong do vat
        FOR(i=1; i<=n; i++) fscanf(input,"%f", &c[i]); // gia tri do vat
        fclose(input);
        printf("\nTrong luong cai tui la: %f", w); // in du lieu da nhap
        printf("\nVec to gia tri do vat: ");
        FOR(i=1; i<=n; i++) printf("%f ", c[i]);
        printf("\nVec to trong luong do vat: ");
        FOR(i=1; i<=n; i++) printf("%f ", a[i]);
        }
    }
    void update()
    {
        int i;
        if(cost>fopt)
        {
            FOR(i=1; i<=n; i++) xopt[i]=x[i];
            fopt=cost;
        }
    }
    void nhanhcan(int i)
    {
        int j,t;
        t=(w-weight)/a[i];
        FOR(j=t; j>=0; j--)
        {
            x[i]=j;
            weight=weight+a[i]*x[i];
            cost=cost+c[i]*x[i];
            if (i==n) update();
            ELSE if (cost+c[i+1]*(w-weight)/a[i+1]>fopt) nhanhcan(i+1);
            weight=weight-a[i]*x[i];
            cost=cost-c[i]*x[i];
        }
    }
    void inkq()
    {
        int i;
        printf("\n\n***Ket qua tinh toan***");
        printf("\nTong gia tri cua cac do vat la: %f", fopt);
        printf("\nPhuong an toi uu la: ");
        FOR(i=1; i<=n; i++) printf("\nSo luong do vat %d la %d", ind[i], xopt[i]);
        printf("\n***********************\n");
        getch();
    }
    void main()
    {
        nhapfile();
        batdau();
        nhanhcan(1);
        inkq();

    Chú ý bài sưu tầm này không giống đề thầy ra, chỉ để tham khảo thôi.



    Được sửa bởi Admin ngày Tue Dec 13, 2011 8:13 pm; sửa lần 2.


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    hailv


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Anh Cường Post lại đề bài tập thầy ra phát! Thầy nói nhỏ không nghe rõ.

    Admin trả lời:
    Đề thầy ra:

    Viết lời giải bài toán cái túi với dữ liệu sau:
    [You must be registered and logged in to see this image.]

    Nghĩa là làm sao để tổng giá trị trong túi là lớn nhất.

    [You must be registered and logged in to see this image.]

    Nghĩa là làm sao để tổng trọng lượng không vượt quá sức chứa của túi.

    Chú ý rằng, bài toán mẫu thì xi Э {0, 1} nhưng bài toán này xi Э {0, 1, ..., ci}
    Nghĩa là bài toán này, một vật có thể lấy nhiều lần vào túi, ở đây là ci lần vào túi. Cho nên thầy yêu cầu nêu hướng giải quyết của giải thuật, giải thích và đề xuất đoạn code giả mã.

    Trong đó:
    Vi chỉ giá chỉ của vật thứ i
    Wi chỉ trọng lượng của vật thứ i
    xi số lần lấy vật thứ i, có thể thay xi = 0, nghĩa là không lấy vật ấy, hoặc có thể lấy 1 đến ci lần vật thứ i.

    3 knapsack algorithm on Tue Dec 13, 2011 6:21 pm

    r0langtu


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    chúc mọi người học tốt.
    p: tui đọc mà cũng chưa hỉu lém!
    [You must be registered and logged in to see this link.]

    http://www.facebook.com/vinhhanh.tran

    Admin


    Quản trị viên
    Quản trị viên
    Có tin mới đây, down ngay:
    Download toàn bộ bài giảng của thầy trong phần này

    Nói lại:

    Khi các bạn click vào các link Download này, trình duyệt sẽ chuyển sang các link của Adf.ly, đây là một bất tiện nho nhỏ nhưng sẽ giúp ích chúng ta có kinh phí duy trì Website, rất mong các bạn thông cảm cho sự bất tiện này. Để Download bất cứ file nào qua Adf.ly, bạn chờ trong khoảng 5giây, khi nút bấm có chữ "SKIP AD"(Tiếng Anh) hoặc "Bỏ qua quảng cáo" ở góc trên bên phải, bạn bấm vào nút này (xem minh họa phía dưới).

    [You must be registered and logged in to see this image.]


    Chờ và bấm nút SKIP AD để hiển thị ra link gốc của mediafire, ví dụ link sau:



    [You must be registered and logged in to see this image.]


    Khi Adf.ly chuyển sang link gốc Mediafire thì bạn Download như bình thường


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    HaiYen


    Thành viên cao cấp
    Thành viên cao cấp
    Em down thấy phần bài giảng của thầy cũng đã có code của 2 phần:

    Bài xếp ba lô dạng 0-1


    Hạn chế số đồ vật thuộc mỗi loại là 0 (không được chọn) và 1 (được chọn).

    Bài xếp ba lô 0-1 có thể được phát biểu bằng toán học như sau:Cực đại hóa [You must be registered and logged in to see this image.]sao cho [You must be registered and logged in to see this image.]
    Bài xếp ba lô bị chặn hạn chế số đồ vật thuộc mỗi loại không được vượt quá một lượng nào đó.

    Bài xếp ba lô bị chặn có thể được phát biểu bằng toán học như sau:Cực đại hóa [You must be registered and logged in to see this image.]sao chp [You must be registered and logged in to see this image.]
    Bài xếp ba lô không bị chặn không có một hạn chế nào về số lượng đồ vật mỗi loại.
    Trong đó các phần 0-1 và không bị chặn thầy đã viết, nên các anh chị nếu có viết thì viết vào phần thầy chưa viết theo đề thầy ra là Bài xếp ba lô bị chặn hạn chế số đồ vật thuộc mỗi loại không được vượt quá một lượng nào đó. Ví dụ
    - Số lượng đồ vật n = 4
    - Trọng lượng cái túi m = 11
    [You must be registered and logged in to see this image.]

    [You must be registered and logged in to see this image.]
    Đây là hướng giải quyết em đề xuất để anh chị tham khảo: (thuật toán Greedy)
    B1: Sắp xếp các đồ vật theo thứ tự giảm dần của thương số "V/W" → ta thu được các phương án Gj, j = 1..3.
    B2:
    Gọi Ij là lời giải thu được theo thuật toán Gj. Gọi I4 là lời giải đạt
    max{∑(iЄ I1)Ci, ∑(iЄ I3)Ci}. I4 thỏa mãn: ∑(iЄ I4)Ci >= (1/2)f*

    - Phương án tối ưu: Chọn đồ vật 2, 3 và giá trị tối ưu f = 28.


    ================
    Nhà em cách 4 quả đồi
    Cách 3 con suối, cách đôi cánh rừng
    Nhà em xa cách quá chừng
    Em van anh đấy, anh đừng yêu em!...

    FaceBook của em

    Tongmanhcuong


    Thành viên cao cấp
    Thành viên cao cấp
    Để giải quyết bài toán cái túi thì có rất nhiều cách giải. Cách giải mà mọi người post lên là dùng phương pháp nhánh cận.
    Còn cách của thày là dùng tư tưởng của Qui hoạch động.

    Thanks FOR uploading the slide of lecture.


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

    7 Bounded knapsack problem on Tue Dec 13, 2011 9:59 pm

    xuandiencntt


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    anh em nào đọc hiểu được thì viết lại cho mọi người xem với nhé. Mình đọc mà thấy rối tung cả lên
    [You must be registered and logged in to see this link.]
    Còn đây là file pdf về bài toán
    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this image.] chắc phải đục đầu ra mất [You must be registered and logged in to see this image.]

    xuandiencntt


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Đã có bác nào có ý tưởng làm bài Bounded knapsack problem chưa?

    Admin


    Quản trị viên
    Quản trị viên
    Theo gợi ý của em Yến và bài giảng của thầy ta có thể trình bày thuật giải như sau:
    1. Đầu tiên sắp xếp giảm dần đánh số lại các đồ vật theo thương số Vi/Wi nhằm mục đích những vật giá trị hơn (theo trọng lượng) sẽ được ưu tiên xếp lên trước.
    Lấy đúng ví dụ mà thầy đưa ra trên lớp nhé. Túi có sức chứa 12 ký. Có các vật sau (tạm ghi ra đây, sau này sẽ sắp xếp lại và gọi theo thứ tự mới):
    + Vật 1, nặng 2 kg, giá trị 2$
    + Vật 2 nặng 7 kg, giá trị 5$
    + Vật 3 nặng 1 kg, giá trị 2$
    + Vật 4 nặng 5 kg, giá trị 4$
    + Vật 5 nặng 4 kg, giá trị 10$

    Vậy tính giá trị/trọng lượng ta sẽ có thứ tự mới như sau, từ đây sẽ làm việc theo thứ tự mới này:
    + Vật 1, nặng 4 kg, giá trị 10$
    + Vật 2 nặng 1 kg, giá trị 2$

    + Vật 3 nặng 2 kg, giá trị 2$

    + Vật 4 nặng 5 kg, giá trị 4$

    + Vật 5 nặng 7 kg, giá trị 5$
    Giả sử cho Ci = 2 để giải.
    2. Kẻ một bảng có các cột mỗi cột là giá trị tăng dần từng ký một, cho đến khi đạt được khối lượng túi. Giả sử túi của chúng ta 12 cân thì phần này kẻ thành 12 cột ghi số cân từ 1 đến 12, mỗi số cân 1 cột. (Phần này gọi là j, theo cách gọi của thầy)
    3. Điền giá trị vào các hàng mỗi hàng điền số loại vật để đưa vào. (Phần này gọi là i theo cách gọi của thầy).
    i
    j = 0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    1
    0












    2
    0












    3
    0












    4
    0












    5
    0












    Viết đoạn code này (của thày đó nhe, đừng có mà thắc mắc vì sao, vì... thầy viết đó)
    Code:
    FOR (i = 0; i ≤ n ; i++)    B[i,0] = 0;
    FOR (j = 0; j ≤ W;j ++)  B[0,j] = 0;
    - Hàm ý của dòng trên nghĩa là điền 1 dãy số 0 ở hàng thứ 2. Nghĩa là nếu không đưa vật gì vào túi, thì giá trị bên trong cái túi ấy cũng chỉ là 0 thôi. Ở đây trong bài giảng của thầy, thì B[i, j] chính là giá trị bên trong cái túi chứa loại vật thứ i và có túi lúc này trọng lượng là j.
    - Hàm ý dòng dưới nghĩa là điền toàn bộ giá trị 0 vào cột j = 0. Nghĩa là khi trọng lượng túi = 0, thì túi chẳng có giá trị nào cả.
    Bây giờ ta tiến hành điền vào bảng. Cái này lại vác thuật toán của thầy ra đã, sau đó mới điền.
    Code:
    FOR (i = 1; i ≤ n; i++ )
                    FOR (j = 1; j ≤ W; j++ )
                          IF  (Wi > j)
                              B[i, j]  =  B[i - 1, j];
                          ELSE
                              B[i, j]  =  max { B[i - 1, j - kWi ] + kVi , k =  0, 1, 2, ...,Ci , j - kWi > 0};
    Nghĩa là thế nào?
    Nghĩa là điền dần vào các ô trong bảng thôi.
    Nếu trọng lượng của vật thứ i mà lớn hơn j thì vật đó sẽ không thể thêm được vào túi, giá trị của túi vẫn chỉ bằng giá trị của trọng lượng túi trước đó thôi (Ở đây rất nguy hiểm, bài giảng của thầy mà các bạn đao về đã đánh nhầm dấu, lẽ ra là dấu > thì thầy lại đánh dấu <, nếu vị nào không tỉnh, ăn đòn ngay).
    Ngược lại, giá trị của túi sẽ lựa chọn lấy giá trị lớn nhất giữa các giá trị:
    B[i - 1, j - kWi ] + kVi trong đó k là số lần lấy một phần tử thứ i, và k phải nhỏ hơn Ci (số lần tối đa lấy 1 phần tử).
    Thế thôi.
    Chép thì chép, hưng phải modify đi đó nhé, tôi học dốt nên viết tạm ra như vậy để các bạn góp ý để bài làm tốt nhất cho mọi người nhé.
    Vậy bảng phải điền là:
    i
    j = 0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    1
    0
    0
    0
    0
    10
    10
    10
    10
    20
    20
    20
    20
    20
    2
    0
    2
    4
    4
    10
    12
    14
    14
    20
    22
    24
    2424
    3
    0
    2
    4
    4
    10
    12
    14
    14
    20
    22
    24
    24
    26
    4
    0
    2
    4
    4
    10
    12
    14
    14
    20
    22
    24
    24
    26
    5
    0
    2
    4
    4
    10
    12
    14
    14
    20
    22
    24
    24
    26
    Từ đây ta nhận xét, nếu k đủ lớn, túi bé thì nhiều trường hợp sẽ không dùng đến vật ít giá trị (Chỉ thêm vào khi vật giá trị hơn đã hết)


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    huonglt


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Ad ơi, cho mình hỏi chút. Mình làm bài toán về cái túi nhưng là kiểu bài toán không hạn chế số lượng mỗi đồ vật (unbounded knapsack problem). Nhưng mình chỉ mới hiểu về dạng bài toán 0/1 Knapsack thôi. Có bạn nào hiểu về dạng unbounded knapsack problem thì giúp đỡ mình với. Cảm ơn các bạn nhiều.

    Sponsored content


    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of http://khmt.123.st

    Free forum | © PunBB | Free forum support | Liên hệ | Report an abuse | Create a blog