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.

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ì x_i Э {0, 1} nhưng bài toán này x_i Э {0, 1, ..., c_i}
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à c_i 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 đó:
V_i chỉ giá chỉ của vật thứ i
W_i chỉ trọng lượng của vật thứ i
x_i 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 c_i lần vật thứ i.

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.]

Có tin mới đây, down ngay:
[You must be registered and logged in to see this link.]

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).

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.]
Đâ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.

Để 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.

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.]

Đã có bác nào có ý tưởng làm bài Bounded knapsack problem chưa?

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	24	24
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)

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.