Phương pháp quy hoạch động – bài toán ba lô 1

Trong môn phân tích thiết kế giải thuật một trong những phương pháp gây đau đầu nhất đó là phương pháp quy hoạch động hôm nay mình muốn trình bày lại cách cài đặt bài bài toán ba lô 1, một trong những bài toán chọn món hàng nổi tiếng, mọi người góp ý nha!

Bài toán ba lô 1

Đề bài: Cho n món hàng (n ≤ 50). Món thứ i có khối lượng là A[i] (số nguyên). Cần chọn những món hàng nào để bỏ vào một ba lô sao tổng khối lượng của các món hàng đã chọn là lớn nhất nhưng không vượt quá khối lượng W cho trước. (W ≤ 100). Mỗi món chỉ chọn 1 hoặc không chọn.

Bài toán ba lo 1

Bài toán ba lo 1

Input: n W

A[1] A[2] … A[n]

Ví dụ:

4 10
5 2 4 3

OutPut:

Tổng khối lượng của các món hàng bỏ vào ba lô.
Khối lượng của các món hàng đã chọn.

Trong ví dụ trên:

Tổng khối lượng của các món hàng bỏ vào ba lô là 10
Khối lượng các món hàng được chọn: 5 2 3

Hướng giải bài toán ba lô 1

1.Tổ chức dữ liệu

Fx[k, v] là tổng khối lượng của các món hàng bỏ vào ba lô khi có k món hàng đầu tiên để chọn và khối lượng tối đa của ba lô là v. Với k ∈ [1, n], v ∈ [1, W].

Nói cách khác: Khi có k món để chọn, Fx[k, v] là khối lượng tối ưu khi khối lượng tối đa của ba lô là v.
Khối lượng tối ưu luôn nhỏ hơn hoặc bằng khối lượng tối đa: Fx[k, v] ≤ v

Ví dụ: Fx[4, 10] = 8 Nghĩa là trong trường hợp tối ưu, tổng khối lượng của các món hàng được chọn là 8, khi có 4 món đầu tiên để chọn (từ món thứ 1 đến món thứ 4) và khối lượng tối đa của ba lô là 10. Không nhất thiết cả 4 món đều được chọn.

2. Thuật toán tạo bảng

Trường hợp đơn giản chỉ có 1 món để chọn: Ta tính Fx[1, v] với mọi v: Nếu có thể chọn (nghĩa là khối lượng tối đa của ba lô >= khối lượng của các món hàng thứ 1), thì chọn: Fx[1, v] = A[1];

Ngược lại ( v < A[1] ), không thể chọn, nghĩa là Fx[1, v] = 0; Giả sử ta đã tính được Fx[k–1 , v ] đến dòng k–1, với mọi v ∈ [1, W]. Khi có thêm món thứ k để chọn, ta cần tính Fx[k , v] ở dòng k, với mọi v∈[1,W] Nếu có thể chọn món hàng thứ k (v >= A[k]), thì có 2 trường hợp:

Trường hợp 1: Nếu chọn thêm món thứ k bỏ vào ba lô, thì Fx[k, v] = Fx[ k–1 , u ] + A[k]; Với u là khối lượng còn lại sau khi chọn món thứ k. u = v – A[k]

Trường hợp 2: Ngược lại, không chọn món thứ k, thì Fx[k, v] = Fx[k–1, v ];

Trong 2 trường hợp trên ta chọn trường hợp nào có Fx[k, v] lớn hơn.

Ngược lại (v < A[k]), thì không thể chọn, nghĩa là Fx[k, v] = Fx[k–1, v]; Tóm lại: công thức đệ quy là: if (v >= A[k])
Fx[k,v] = Max(Fx[k-1, v - A[k]] + A[k] , Fx[k-1,v])
else
Fx[k,v] = Fx[k-1, v];

Dưới đây là bảng Fx[k,v] tính được trong ví dụ trên:

Thuật toán tạo bảng trong ba lo 1

Thuật toán tạo bảng trong ba lo 1

3. Thuật toán tra bảng để tìm các món hàng được chọn

Chú ý: Nếu Fx[k, v] = Fx[k–1, v] thì món thứ k không được chọn. Fx[n, W] là tổng khối lượng tối ưu của các món hàng bỏ vào ba lô.
Bước 1: Bắt đầu từ k = n, v = W.
Bước 2: Tìm trong cột v, ngược từ dưới lên, ta tìm dòng k sao cho Fx[k,v] > Fx[k–1, v]. Đánh dấu món thứ k được chọn: Chọn[k] = true;
Bước 3: v = Fx[k, v] – A[k]. Nếu v > 0 thì thực hiện bước 2, ngược lại thực hiện bước 4
Bước 4: Dựa vào mảng Chọn để in ra các món hàng được chọn.

Cài đặt bài toán ba lô 1

Đây là một cách cài đặt demo cơ bản mà thg bạn nó cài bằng C, các bạn xem tham khảo nha! Tuy không tối ưu nhưng đã demo được bài toán ba lô 1, các bạn có thể tự phát triển thêm.

<!--
#include<iostream.h>
#include<stdio.h>
#include<conio.h>

void docfile(int a[],int &n,int &w)
{
	FILE *f;
	f=fopen("balo1.txt","rt");
	fscanf(f,"%d%d",&n,&w);
	for(int i=1;i<=n;i++)
		fscanf(f,"%d",&a[i]);
		fclose(f);
}

void ghifile(int Chon[],int A[],int n)
{
	FILE *f;
	f=fopen("kqbalo1.text","wt");
	for(int i=1;i<=n;i++)
		if(Chon[i]==1)
	fprintf(f,"%3d",A[i]);

}

int Max(int a, int b)
{
	if(a>b)
		return a;
	return b;
}

void main()
{
    int Fx[101][101];//bang
    int A[101];//A mang trong luong
	int Chon[101];
    int n;
    int W;
	
	docfile(A,n,W);
	
	//Chua chon mon hang nao gan bang 0.
    for (int k=1;k<=W;k++)
    Fx[0][k]=0;

	// Tao bang
    for (int k=1;k<=n;k++)//k so mon hang, v khoi luong toi da
	{
		for (int v=1;v<=W;v++)
		{
			
			if (v>=A[k])
			{
				Fx[k][v]=Max(Fx[k-1][v-A[k]]+A[k],Fx[k-1][v]);
			}
			else
			{
				Fx[k][v]=Fx[k-1][v];
			}
		}
	}

	// Kiem tra bang tim ra cac mon hang duoc chon
	int v=W;
	int k=n;

	while( v>0)
	{
		for(int k=n;k>=0;k--)
		{
			if(Fx[k][v]>Fx[k-1][v])
			{
				Chon[k]=1;
				v=Fx[k][v]-A[k];
			}
		}
	}
	
	//In cac mon duoc chon
	ghifile(Chon,A,n);
}
-->

Bài này tương tác trên file đây sẽ là kết quả trước và sau khi chạy chương trình.

Kết quả bài toán ba lo 1

Kết quả bài toán ba lo 1

Kết luận: Đây là một phương pháp giải đơn giản bạn nào có cách nào hay thì góp ý nha! Chúc thành công!

VN:F [1.9.22_1171]
Rating: 9.1/10 (11 votes cast)
Phương pháp quy hoạch động - bài toán ba lô 1, 9.1 out of 10 based on 11 ratings
Chuyên mục: Lập Trình C/ C++
Tagged: , , .

Một Comment

  1. Nguyen Ha

    copy paste vao C khong chay, xem lai giup minh voi

Để lại comment của bạn