Bài Toán Chia Kẹo

  -  

Bài toán chia kẹo c++ là một dạng toán điển hình, bài toán này có phương pháp giải đặc biệt, tư tưởng của nó có thể được áp dụng để giải cho rất nhiều bài toán khác trong Tin học Nó còn có tên gọi là Number Partitioning, không có thuật toán tối ưu để giải. Sau đây là những thuật toán từ đơn giản đến khó để giải quyết bài tập này với timhome.vn nhé.

Bạn đang xem: Bài toán chia kẹo

Video hướng dẫn bài toán chia kẹo pascal

Thuật toán chia kẹo

Một bài toán được gọi là một bàitoán hay nếu nó là một bài toán khó và có lời giải độc đáo. Bài toán “Chia kẹo” là một minh chứng cho điềuđó. Bài toán này có phương pháp giải đặc biệt, tư tưởng của nó có thể được ápdụng để giải cho rất nhiều bài toán khác trong Tin học. Các bạn có thể thamkhảo bài viết “Thuật toán chia kẹo và ứng dụng giải lớp bài toán chianhóm” của tác giả Lã Thành Công trên số báo tháng 1/2001. Sauđây tôi xin trình bày phương pháp giải bài toán này và ứng dụng thuật toántrong việc giải các bài toán tin khác.

*

Nhắc lại bài toán chia kẹo

Có N gói kẹo, gói thứ i có Aicái kẹo. Không được bóc bất kỳ một gói kẹo nào, cần chia N gói kẹo thành haiphần sao cho độ chênh lệch số kẹo giữa hai gói là ít nhất.

Dữ liệu vào trong file “chiakeo.inp” có dạng :

– Dòng đầu tiên là số N(N

– Dòng thứ hai là N số Ai(i=1, 2,.., N; Ai

Kết quả ra file “chiakeo.out” có dạng:

– Dòng đầu là độ chênh lệchnhỏ nhất giữa hai phần có thể được.

– Dòng hai là một dãy N số,nếu si =1 thì gói thứ i thuộc phần 1, nếu si =2 thì góithứ i thuộc phần 2

Thuật toán:

Với một số M bất kì, nếu ta biếtđược có tồn tại một cách chọn các gói kẹo để tổng số kẹo của các gói được chọnbằng đúng M không, thì bài toán được giải sẽ quyết. Vì đơn giản là ta chỉ cầnchọn số M sao cho M gần với

*
Ai/2nhất (với i =1,2,..,N). Sau đó xếp các gói kẹo để tổng bằng M vào phần một,phần thứ hai sẽ gồm các gói kẹo còn lại. Để kiểm tra được điều trên ta sẽ xâydựng tất cả các tổng có thể có của N gói kẹo bằng cách: ban đầu chưa có tổngnào được sinh ra. Làm lần lượt với các gói kẹo từ 1 đến N, với gói kẹo thứ i,ta kiểm tra xem hiện tại có các tổng nào đã được sinh ra, giả sử các tổng đó làx1, x2,.., xt vậy thì đến bước này sẽ có thểsinh ra các tổng x1, x2,.., xt và Aivà x1+Ai,x2+Ai,..,xt+Ai.Với N gói kẹo, mà mỗi gói có không quá 100 cái kẹo vậy tổng số kẹo không vượtquá N*100 0 do {lan nguoc mang c tim cac phan tu ta cong vao de duoc m}begins>:=1;{phan tu nao da cho vao tong thi danh dau la 1}m:=m-a>;end;{--------ghi ket qua-----------}assign(f,"chiakeo.out");rewrite(f);writeln(f,sum-2*tu); {sum-2*m la khoang cach giua 2 phan}for i:=1 to n do write(f,s," ");close(f);END.

Bài toán chia kẹo quy hoạch động

Ý tưởng: Gọi T là tổng số kẹo của N gói. Chúng ta cần tìm số S lớn nhất thỏa mãn: S _ Hướng dẫn giải QHĐ: + Giống như bài bán hoa, nhưng khác ở hàm tính giá trị. Việc tạo bảng QHĐ: Chỉ cần duyệt n túi kẹo và Tổng/2 kẹo. dữ liệu sẽ lưu trong mảng L(n , T/2). Xác định Hàm tính tại mỗi thời điểm: việc chọn dựa vào điều kiện: KHÔNG LẤY túi thứ i khi và chỉ khi (L > L> + A) Hoặc (L> +A L> + A nghĩa là giá trị của khi không lấy túi i ( L) lớn hơn khi lấy loại i (L> + A). L> +A Var i: integer; Begin i:=n; While i 0 do Begin If LL then Begin Write(fo,i, ‘ ‘); m:=m-a; End; i:= i-1; End; end;

Ứng dụng giải bài toán CÁC THANH GỖ (đề Lâm Đồng)

Trong một buổi cắm trại của lớp, bạn An mua N thanh gỗ có độ dài mỗi thanh là L. Khi cắm trại, các bạn của An cưa các thanh gỗ ra một cách ngẫu nhiên (có độ dài là số nguyên).

Về sau các bạn có ý định gắn các mẩu con để khôi phục lại các thanh gỗ ban đầu nhưng lại quên mất độ dài L. Họ đã quyết định nối lại các thanh gỗ sao cho chúng có độ dài bằng nhau.

Xem thêm: Những Đột Phá Quy Hoạch Sân Bay Nội Bài Sẽ Mở Rộng Gấp Rưỡi, Mở Rộng Sân Bay Nội Bài

Hãy giúp họ chọn cách nối sao cho chúng có độ dài như nhau và càng ngắn càng tốt.

Dữ liệu vào: cho trong file văn bản THANHGO.INP:

– Dòng đầu ghi số N (N£50) là số lượng các mẩu gỗ.

– N dòng tiếp theo mỗi dòng ghi số nguyên Li (1 £ Li £ 100, 1 £ i £ N) thể hiện độ dài của mẩu gỗ thứ i.

Kết quả: Ghi ra file văn bản THANHGO.OUT

– Dòng đầu tiên ghi độ dài ngắn nhất tìm được.

Xem thêm: Đi Tàu Viễn Dương Là Gì - Những Thủy Thủ Tàu Viễn Dương Bật Khóc Trên Biển

– Trên mỗi dòng ghi số hiệu các mẩu gỗ dùng để ghép thành thanh gỗ đó.

Áp dụng bài toán chia nhóm trên để giải:

Program thanh_go;Var dem,k,n,i,j,L1,LL,T: word;luu,L,lvt,free,s: array<1..50> of byte;procedure doc;var f:text;beginassign(f,"thanh_go.inp"); reset(f);readln(f,n);T:=0;for i:=1 to n dobeginread(f,L);lvt:=i;T:=T+L;end;close(f);s:=L;end;procedure sapxep;beginfor i:=1 to n-1 dofor j:=i+1 to n doif l0 do {lan nguoc mang c tim cac phan tu ta cong vao}beginluu>:=dem;{phan tu nao da cho vao tong thi danh dau}free>:=1;k:=k-L>;end;end else ktra:=false;end;procedure inkq;var i,j:byte;f:text;beginassign(f,"thanh_go.out"); rewrite(f);writeln(f,L1);k:=T div L1;for i:=1 to k dobeginfor j:=1 to n doif luu=i then write(f,lvt," ");writeln(f);end;close(f);end;{--------chuong trinh chinh-----------}begindoc;sapxep;For L1:=LL to T doif T mod L1 =0 thenbegink:=T div L1; dem:=0;For i:=1 to n do free:=0;for i:=1 to n do luu:=0;repeatktra(L1);until (dem=k)or(ktra(L1)=false);if dem=k thenbegininkq;break; {neu tim duoc ket qua thi thoat vong lap for kiem tra}end;end;end.