Hướng Dẫn Giải Bài Toán Cái Túi Và Những Ứng Dụng Xung Quanh Nó

một phần của tài liệu PHÂN TÍCH THIẾT KẾ THUẬT TOÁN VÀ ĐÁNH GIÁ ĐỘ PHỨC TẠP CỦA GIẢI THUẬT - ĐH SƯ PHẠM HÀ NỘI (Trang 55 -57 )

3. Một trong những ví dụ minh họa

3.4. Bài toán cái túi

Bài toán 3.4. Mang đến n dụng cụ (n ≤ 100), đồ vật thứ i tất cả trọng lượng là wi (wi ≤ 100) và có mức giá trị áp dụng là ci (ci ≤ 100). đề nghị xếp đồ vật vào một cái túi làm thế nào cho tổng giá chỉ trị thực hiện được xếp vào bên trong túi là to nhất. Biết rằng cái túi chỉ rất có thể mang được trọng lượng không vượt thừa b (b ≤ 100).

a) Phương pháp qui hoạch động

Bước 1. Nêu giảđịnh về hàm qui hoạch động

Gọi f(i, j) là cực hiếm sử dụng lớn số 1 của của những đồ thứ được xếp vào túi lúc chọn các đồ thứ 1, 2, …, i cùng trọng lượng số lượng giới hạn của túi là j. Lúc ấy giá trị nghiệm rất tốt của việc là f(n, m).

Bước 2:Tìm nghiệm của các bài toán con đơn giản và dễ dàng

Dễ thấy f(0, j) = 0 với đa số j = 1, 2, …, b

Bước 3: Xây dựng cách làm qui hoạch hễ

Với số lượng giới hạn trọng lượng j, việc chọn tối ưu trong những đồ trang bị 1, 2, …, i - 1, i để có giá trị lớn số 1 có nhị khả năng:

• còn nếu không chọn đồ vật thứ i thì f(i, j) là quý giá sử dụng lớn nhất có thể bằng cách chọn trong các đồ đồ dùng 1, 2, …, i - 1 với trọng lượng j, tức là

f(i, j) = f (i-1, j)

• Nếu tất cả chọn đồ vật i (với wi ≤ j) thì f(i, j) bởi giá trị áp dụng của đồ vật thứ i cộng với giá trị áp dụng lớn nhất rất có thể được bằng phương pháp chọn trong những các gói 1, 2, …, i - 1 với giới hạn trọng lượng là j - wi. Có thể nói rằng ta gồm công thức:

f(i, j) = ci + f(i-1, j - wi)

Kết thích hợp hai năng lực trên ta gồm công thức qui hoạch động: f(i, j) = max f(i-1, j) , ci + f(i-1, j - wi) cùng với i = 1, 2, …, n cùng j = 0, 1, 2, .., M.

Bước 4. Tìm kiếm lại nghiệm

Ta nhất quán hàm f(i,j) cùng với bảng F<1..n, 1..b> (còn gọi là bảng qui hoạch động). Sau khi tính xong xuôi mảng F, bài toán truy lốt trên F để tìm nghiệm như sau:

Chú ý rằng F là giá chỉ trị thực hiện lớn nhất của những đồ đồ được xếp vào túi khi chứng kiến tận mắt xét tất cả n dụng cụ và số lượng giới hạn trọng lượng của túi là b.

Nếu F = F thì tức là không chọn dụng cụ thứ n, ta truy vấn tiếp F. Còn ví như F ≠ F thì minh chứng đồ vật thiết bị n được chọn, ta ghi thừa nhận thành phần kia vào nghiệm và truy tiếp F. Cứ liên tiếp quá trình đó cho đến khi truy lên tới hàng thiết bị 0 của bảng F.

b) tế bào phỏng Pascal procedure Caitui; begin for j := 0 lớn b do F<0, j> := 0; for i := 1 lớn n vị for j := 1 lớn b vày begin F := F;

if (j > wi) và (F i> + ci then F := F

end; end; procedure Trace; begin write(‘Max value: ‘, F); while n ≠ 0 vị begin if F ≠ F then begin

write(‘Chon bởi vat ‘, n, ‘ w = ‘, wn, ‘ value = ‘, vn); b := b - wn;

end; n := n - 1; end;

một trong những phần của tư liệu PHÂN TÍCH THIẾT KẾ THUẬT TOÁN VÀ ĐÁNH GIÁ ĐỘ PHỨC TẠP CỦA GIẢI THUẬT - ĐH SƯ PHẠM HÀ NỘI (Trang 55 -57 )

I. Bài toán Cái túi và những bài toán áp dụng

1. Lời mở đầu

Bài toán Cái túi, Bài toán Xếp ba lô, Bài toán Knapsack,...là những tên gọi khác nhau mà chúng ta thường nghe đến, mà lại tất cả đều dùng để chỉ bình thường một bài toán tối ưu hóa tổ hợp, trong đó ta cần phải lựa chọn một số đồ vật để nhét vào một chiếc túi với tải trọng biết trước, sao cho tổng giá trị của các đồ vật nhét vào là lớn nhất có thể. Bài toán này đã được nghiên cứu trong rộng một thế kỷ, và nó là một vào những bài toán có ứng dụng vô cùng lớn lớn vào thực tế.

Bạn đang xem: Hướng dẫn giải bài toán cái túi

Có rất nhiều dạng khác nhau của bài toán cái túi mà tôi đã giới thiệu tới các bạn ở những chăm đề trước. Những dạng tiêu biểu của bài toán này có thể kể đến là:

Bài toán Knapsack với các giá trị số thực: Trọng lượng và giá trị của các món đồ là số thực. Bài toán này chỉ có thể giải quyết bằng phương pháp con quay lui (hoặc cải tiến bằng Nhánh cận).Bài toán Knapsack cho phép cắt nhỏ đồ vật (Fractional Knapsack): Các đồ vật được phép cắt ra và lấy một phần. Bài toán này có thể giải quyết bằng phương pháp Tham lam.Bài toán Knapsack 0−10 - 10−1: Các vật chỉ có thể chọn hoặc ko chọn, ngoài ra giá trị và trọng lượng của các vật đều là số nguyên. Bài toán này có thể giải bằng phương pháp Quy hoạch động.

Trong bài viết này, chúng ta sẽ cùng tập trung nghiên cứu bài toán Knapsack 0−10 - 10−1 và một số ứng dụng của nó vào việc giải những bài toán Quy hoạch động có bốn duy tương tự.

2. Phát biểu bài toán

Cho nnn đồ vật khác nhau, đồ vật thứ iii có trọng lượng wiw_iwi và giá trị viv_ivi. Bạn có theo một chiếc túi có tải trọng tối nhiều là W,W,W, nhiệm vụ của bạn là chọn ra các đồ vật để đến vào túi làm thế nào để cho tổng giá trị của các đồ vật lấy được là lớn nhất có thể?

Input:

Dòng đầu tiên chứa hai số nguyên dương nnn và WWW.nnn dòng tiếp theo, mỗi dòng chứa nhị số nguyên dương wiw_iwi và viv_ivi phân tách nhau bởi dấu cách.

Output:

Dòng đầu tiên in ra tổng giá trị lớn nhất của các vật lấy được.Dòng thứ nhị in ra chỉ số của các vật được lựa chọn theo thứ tự tăng dần.

Sample Input:

3 5010 6020 10030 120Sample Output:

2202 3

3. Ý tưởng

Gọi dpdpdp là tổng giá trị lớn nhất của các đồ vật lấy được khi chọn trong các đồ vật từ 111 tới iii và giới hạn tổng trọng lượng của chúng là jjj. Kết quả của bài toán là tổng giá trị lớn nhất chọn được vào nnn vật với giới hạn trọng lượng là W,W,W, sẽ chính là dpdpdp.
Xét đồ vật thứ i,i,i, và giới hạn trọng lượng hiện tại là j,j,j, ta có nhì phương án để lựa chọn:
Nếu vật thứ iii không được chọn vào phương án tối ưu, thì kết quả tối ưu sẽ được chọn vào (i−1)(i - 1)(i−1) đồ vật trước đó với giới hạn trọng lượng vẫn là jjj.Nếu vật thứ iii được chọn vào phương án tối ưu, thì tải trọng còn lại có thể sử dụng là (j−wi)(j - w_i)(j−wi) mang lại (i−1)(i - 1)(i−1) đồ vật phía trước, và ta được thêm giá trị viv_ivi của vật thứ iii. Dĩ nhiên, trường hợp này chỉ xét đến khi j≥wij ge w_ij≥wi.
Dễ thấy rằng, nếu như jwij jwi thì chỉ có duy nhất cách lựa chọn đầu tiên, còn nếu j≥wij ge w_ij≥wi thì có thể lựa chọn theo cả hai cách để lấy cách tốt hơn. Tổng hợp lại, ta có công thức quy hoạch động:
dp={dp;if wi>j.max(dp,dp+vi);if wij.dp = egincases dp; & extif w_i > j. \ extmaxig(dp, dp + v_iig); & extif w_i dp={dp;max(dp,dp+vi);if wi>j.if wij.
Cơ sở quy hoạch động dễ thấy là dp<0>=0,dp<0> = 0,dp<0>=0, vì giá trị lớn nhất có thể chọn được vào số 000 đồ vật thì vẫn là 000.
Để tầm nã vết lại các món đồ được chọn, ta sẽ đi ngược về bên trên bảng phương án, bắt đầu từ vị trí kết quả là dpdpdp (hàng n,n,n, cột WWW). Nếu như dp=dpdp = dpdp=dp tức là món đồ thứ nnn ko được chọn, ta tầm nã ngược về dpdpdp. Ngược lại nếu dp≠dpdp e dpdp=dp nghĩa là phương án lựa chọn tối ưu có chứa món đồ thứ nnn và truy hỏi ngược lên dpdpdp. Tiếp tục như vậy cho tới lúc đi về tới hàng 000 của bảng phương án (tức là cơ sở quy hoạch động) thì dừng lại.
4. Cài đặt
Ngôn ngữ C++:
#include using namespace std;void enter(int &n, int &W, vector pair int, int > > items) cin >> n >> W; items.resize(n + 1); // Sử dụng kiểu pair để nhập dữ liệu các món đồ. // items.first và items.second lần lượt là trọng lượng và giá trị của đồ vật thứ i. For (int i = 1; i n; ++i) cin >> items.first >> items.second;// truy nã vết các món đồ được chọn.void trace_back(int n, int W, vector vector int > > &dp, vector pair int, int > > &items) vector int > picked_items; while (n > 0) if (dp == dp) --n; else picked_items.push_back(n); W -= items.second; --n; for (int i = picked_items.size() - 1; i >= 0; --i) cout picked_items " ";// Quy hoạch động.void solution(int n, int W, vector pair int, int > > &items) vector vector int > > dp(n + 1, vector int >(W + 1, 0)); for (int i = 1; i n; ++i) for (int j = 0; j W; ++j) dp = dp; if (j >= items.first) dp = max(dp, dp.first> + items.second); // In kết quả. Cout dp endl; trace_back(n, W, dp, items);main() int n, W; vector pair int, int > > items; enter(n, W, items); solution(n, W, items);Ngôn ngữ Python:
def enter(n, W, items): n, W = map(int, input().split()) items = <(0, 0) for _ in range(n + 1)> for i in range(1, n + 1): items = map(int, input().split())def trace_back(n, W, dp, items): picked_items = <> while n > 0: if dp == dp: n += 1 else: picked_items.append(n) W -= items<0> n += 1 print(reverse(picked_items))def solution(n, W, items): dp = <<0> * (W + 1) for _ in range(n + 1)> for i in range(1, n + 1): for j in range(0, W + 1): dp = dp if j >= items<0>: dp = max(dp, dp<0>> + items<1>) print(dp) trace_back(n, W, dp, items)II. Một số bài toán ứng dụng
1. Bài toán Cái túi vô hạn
Đề bài
Một tên trộm mang theo một chiếc túi có tải trọng WWW vào vào một tiệm đá quý. Vào tiệm có nnn loại đá quý, loại thứ iii có khối lượng wiw_iwi và giá trị vi,v_i,vi, với số lượng viên đá mỗi loại là không giới hạn. Thương hiệu trộm cần chọn ra một số viên đá quý để sở hữu theo thế nào cho tổng giá trị của chúng là lớn nhất có thể.
Xác định tổng giá trị đá quý lớn nhất mà tên trộm có thể mang theo với chiếc túi tải trọng W?
W?
W?
Input:
Dòng đầu tiên chứa hai số nguyên dương nnn và W (1≤n,W≤1000)W (1 le n, W le 1000)W (1≤n,W≤1000).nnn dòng tiếp theo, mỗi dòng chứa hai số nguyên dương wiw_iwi và viv_ivi phân tách nhau bởi dấu cách (1≤wi,vi≤100;∀i:1≤i≤n)(1 le w_i, v_i le 100; forall i: 1 le i le n)(1≤wi,vi≤100;∀i:1≤i≤n).
Output:
Dòng đầu tiên in ra tổng giá trị lớn nhất của các viên đá quý mà tên trộm lấy được.Dòng thứ nhì in ra nnn số nguyên c1,c2,…,cnc_1, c_2, dots, c_nc1,c2,…,cn với cic_ici là số lần được chọn của viên đá quý thứ iii.
Sample Input:
2 1001 150 30Sample Output:
100100 0Explanation:
Có rất nhiều cách để thương hiệu trộm sở hữu theo các viên đá quý:
Mang theo 222 viên có khối lượng 50,50,50, tổng giá trị là 606060.Mang theo 100100100 viên có khối lượng 1,1,1, tổng giá trị là 100100100.Mang theo 111 viên có khối lượng 505050 và 505050 viên có khối lượng 1,1,1, tổng giá trị là 808080.
Xem thêm: Ga vé tàu quảng ngãi đi đà nẵng, giá rẻ thống nhất bắc nam
Vậy ta chọn phương án thứ 222.
Ý tưởng
Khác với bài toán cái túi bản gốc, ở bài toán này chúng ta được phép chọn một đồ vật nhiều lần. Nghĩa là ở mọi thời điểm lựa chọn, tất cả các đồ vật đều có thể được sử dụng.
Vì thế, ta chỉ cần sử dụng mảng một chiều dpdpdp với ý nghĩa là tổng giá trị đá quý lớn nhất thu được với giới hạn tải trọng là iii rứa vì mảng nhị chiều như bài toán gốc. Xét giới hạn tải trọng iii và viên đá quý có khối lượng wj,w_j,wj, giá trị vjv_jvj. Nếu như i≥wji ge w_ji≥wj thì ta lại có thể lựa chọn viên đá này vào tập các viên đá được chọn. Từ đó hình thành công thức:
dp=max(dp+vj);∀j:1≤j≤n and i≥wjdp = extmaxig(dp + v_jig); forall j: 1 le j le n ext và i ge w_jdp=max(dp+vj);∀j:1≤j≤n and i≥wj
Kết quả cuối cùng tất nhiên là dpdpdp.
Để truy vết, ta sử dụng một mảng chosen_times extchosen\_timeschosen_times là số lần được chọn của viên đá quý thứ iii. Bắt đầu từ vị trí dpdpdp bên trên bảng phương án. Duyệt qua từng viên đá quý, nếu như tới viên thứ iii mà dp=dp+vidp = dp + v_idp=dp+vi thì viên đá thứ iii được chọn 111 lần, cập nhật tăng vị trí chosen_times extchosen\_timeschosen_times thêm 111 và tróc nã ngược về vị trí dpdpdp trên bảng phương án. Cứ làm như vậy đến tới lúc W=0W = 0W=0 thì dừng lại.
Ta sẽ thu được giải thuật có độ phức tạp O(W×n)O(W imes n)O(W×n).
Cài đặt
Ngôn ngữ C++:
#include using namespace std;void enter(int &n, int &W, vector pair int, int > > gems) cin >> n >> W; gems.resize(n + 1); for (int i = 1; i n; ++i) cin >> gems.first >> gems.second;void trace_back(int n, int W, vector int > &dp, vector pair int, int > > &gems) vector int > chosen_times(n + 1, 0); while (W != 0) for (int i = 1; i n; ++i) if (dp == dp.first> + gems.second) W -= gems.first; ++chosen_times; break; for (int e: chosen_times) cout e " ";void solution(int n, int W, vector pair int, int > > gems) vector int > dp(W + 1, 0); for (int i = 0; i W; ++i) for (int j = 1; j n; ++j) if (i >= gems.first) dp = max(dp, dp.first> + gems.second); cout dp endl; trace_back(n, W, dp, gems);main() int n, W; vector pair int, int > > gems; enter(n, W, gems); solution(n, W, gems);Ngôn ngữ Python:
def enter(n, W, gems): n, W = map(int, input().split()) gems = <(0, 0) for i in range(n + 1)> for i in range(1, n + 1): gems = map(int, input().split())def trace_back(n, W, dp, gems): chosen_times = <0 for i in range(n + 1)> while W != 0: for i in range(1, n + 1): if dp == dp<0>> + gems<1>: W -= gems<0> chosen_times += 1 break print(chosen_times)def solution(n, W, gems): dp = <0 for i in (W + 1)> for i in range(W + 1): for j in range(1, n + 1): if i >= gems<0>: dp = max(dp, dp<0>> + gems<1>) print(dp) trace_back(n, W, dp, gems)if __name__ == "__main__": n, W = 0, 0 gems = <> enter(n, W, gems) solution(n, W, gems)
2. Dãy con tổng bằng K
Đề bài
Cho một dãy số AAA gồm nnn phần tử nguyên a1,a2,…,ana_1, a_2, dots, a_na1,a2,…,an và một số nguyên KKK. Hãy đếm số dãy bé không liên tiếp của dãy AAA có tổng đúng bằng K?
K?
K?
Input:
Dòng đầu tiên chứa nhị số nguyên nnn và K (1≤n≤1000;1≤K≤1000)K (1 le n le 1000; 1 le K le 1000)K (1≤n≤1000;1≤K≤1000).Dòng thứ hai chứa nnn số nguyên a1,a2,…,ana_1, a_2, dots, a_na1,a2,…,an phân tách nhau bởi dấu cách (1≤ai≤1000;∀i:1≤i≤n)(1 le a_i le 1000; forall i: 1 le i le n)(1≤ai≤1000;∀i:1≤i≤n).
Output:
Số nguyên duy nhất là số lượng dãy bé có tổng bằng KKK. Kết quả có thể rất lớn, đề nghị hãy in ra phần dư của kết quả sau thời điểm chia mang lại 109+710^9 + 7109+7.
Sample Input:
4 61 2 3 3Sample Output:
3
Ý tưởng
Dễ nhận thấy, có tổng cộng 2n2^n2n dãy con, đề nghị phương pháp xoay lui duyệt mọi dãy nhỏ là hoàn toàn ko khả thi.
Ý tưởng ở phía trên là sử dụng quy hoạch động với tứ duy giống như bài toán cái túi. Gọi dpdpdp là số lượng dãy nhỏ chọn ra vào mảng bé A<1...i>A<1...i>A<1...i> có tổng là jjj. Lúc xét tới phần tử ai,a_i,ai, ta có thể:
Không chọn aia_iai vào dãy con, lúc đó tổng số dãy con tạo ra sẽ là từ mảng nhỏ A<1...i−1>A<1...i - 1>A<1...i−1> với tổng là j,j,j, số lượng là dpdpdp. Trường hợp này có thể xảy ra với cả jaij jai hay j≥aij ge a_ij≥ai.Chọn aia_iai vào dãy con, lúc đó ta còn lại tổng bằng (j−ai)(j - a_i)(j−ai) phải tạo ra từ mảng nhỏ A<1...i−1>,A<1...i - 1>,A<1...i−1>, số dãy nhỏ tạo ra cũng sẽ tương ứng là dpdpdp. Dễ thấy trường hợp này chỉ xảy ra nếu như j≥aij ge a_ij≥ai.
Vậy ta có công thức truy hỏi hồi:
dp={dp;∀jai.dp+dp;∀j≥ai.dp = egincasesdp; &forall j dp={dp;dp+dp;∀jai.∀j≥ai.
Kết quả cuối cùng sẽ là dpdpdp.
Cơ sở quy hoạch động như sau: dp<0>=1,dp<0> = 1,dp<0>=1, vì luôn luôn có một dãy bé rỗng tổng bằng 000 chọn trong mảng bé A<1...i>A<1...i>A<1...i>. Tất nhiên, dp<0><0>dp<0><0>dp<0><0> cũng bằng 111.
Độ phức tạp giải thuật: O(n×K)O(n imes K)O(n×K).
Cài đặt
Ngôn ngữ C++:
#include using namespace std;const long long hack = 1e9 + 7;void enter(int &n, int &K, vector int > &a) cin >> n >> K; a.resize(n + 1); for (int i = 1; i n; ++i) cin >> a;void solution(int n, int K, vector int > &a) vector vector long long > > dp(n + 1, vector long long > (K + 1, 0)); for (int i = 0; i n; ++i) dp<0> = 1; for (int i = 1; i n; ++i) for (int j = 1; j K; ++j) dp = dp; if (j >= a) (dp += dp>) %= mod; cout dp;main() int n, K; vector int > a; enter(n, K, a); solution(n, K, a);Ngôn ngữ Python:
def solution(n, K, a): gian lận = 10 ** 9 + 7 dp = <<0> * (K + 1) for _ in range(n + 1)> for i in range(n + 1): dp<0> = 1 for i in range(1, n + 1): for j in range(1, K + 1): dp = dp if j >= a: dp = (dp + dp>) % gian lận print(dp)if __name__ == "__main__": n, K = map(int, input().split()) a = <0 for i in range(n + 1)> for i in range(1, n + 1): a = int(input()) solution(n, K, a)III. Tài liệu tham khảo