Một bài toán được gọi là một bàitoán hay ví như nó là một trong bài toán cực nhọc và có giải thuật độc đáo. Việc “Chia kẹo” là 1 trong minh triệu chứng cho điềuđó. Bài toán này có cách thức giải quánh biệt, bốn tưởng của nó có thể được ápdụng để giải cho không ít bài toán không giống trong Tin học. Các chúng ta cũng có thể thamkhảo nội dung bài viết “Thuật toán phân chia kẹo và áp dụng giải lớp việc chianhóm” của người sáng tác 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 thức giải vấn đề này và vận dụng thuật toántrong bài toán giải những bài toán tin khác.
Bạn đang xem: Bài toán chia kẹo
Nhắc lại việc chia kẹo
Có N gói kẹo, gói thứ i tất cả Aicái kẹo. Không được bóc bất kỳ một gói kẹo nào, yêu cầu chia N gói kẹo thành haiphần sao cho độ chênh lệch số kẹo thân hai gói là không nhiều nhất.
Dữ liệu vào trong tệp tin “chiakeo.inp” bao gồm dạng :
– Dòng trước tiên là số N(N
– mẫu thứ nhị là N số Ai(i=1, 2,.., N; Ai
Kết quả ra file “chiakeo.out” tất cả dạng:
– loại đầu là độ chênh lệchnhỏ độc nhất giữa nhì phần có thể được.
– dòng hai là 1 trong dãy N số,nếu mê mẩn =1 thì gói sản phẩm i thuộc phần 1, nếu yêu thích =2 thì góithứ i trực thuộc phần 2
Thuật toán:
Với một số trong những M bất kì, giả dụ ta biếtđược bao gồm tồn tại một bí quyết chọn các gói kẹo để tổng số kẹo của những gói được chọnbằng đúng M không, thì việc được giải đang quyết. Vì đơn giản là ta chỉ cầnchọn số M làm thế nào cho M sát với
Ai/2nhất (với i =1,2,..,N). Kế tiếp xếp những gói kẹo để tổng bởi M vào phần một,phần máy hai vẫn gồm các gói kẹo còn lại. Để chất vấn được điều trên ta đang xâydựng tất cả các tổng rất có thể có của N gói kẹo bởi cách: ban đầu chưa tất cả tổngnào được sinh ra. Làm cho lần lượt với các gói kẹo từ là một đến N, với gói kẹo máy i,ta kiểm soát xem bây giờ có các tổng nào đã làm được sinh ra, trả sử những tổng đó làx1, x2,.., xt vậy thì đến bước này sẽ sở hữu thểsinh ra các tổng x1, x2,.., xt cùng Aivà x1+Ai,x2+Ai,..,xt+Ai.Với N gói kẹo, cơ mà mỗi gói có không thật 100 mẫu kẹo vậy tổng số kẹo không vượtquá N*100 0 bởi vì lan nguoc với c tim cac phan tu ta cong vao de duoc mbegins
Ứng dụng giải việc CÁC THANH GỖ (đề Lâm Đồng)
Trong một buổi cắm trại của lớp, bạn An sở hữu N thanh gỗ có độ dài mỗi thanh là L. Lúc cắm trại, các bạn của An cưa các thanh gỗ ra một cách bỗng nhiên (có độ nhiều năm là số nguyên).Về sau các bạn tất cả ý định gắn những mẩu nhỏ để phục hồi lại những thanh gỗ lúc đầu nhưng lại bỏ quên độ lâu năm L. Họ đã quyết định nối lại các thanh gỗ làm thế nào cho chúng gồm độ dài bởi nhau.
Xem thêm: Lời Bài Hát Những Cô Nàng Ham Vật Chất, Những Cô Nàng Ham Vật Chất
Hãy giúp họ chọn cách nối làm sao để cho chúng gồm độ dài hệt nhau và càng ngắn càng tốt.
Dữ liệu vào: đến trong tệp tin 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 sau 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ỗ sản phẩm i.
Kết quả: Ghi ra tệp tin văn bạn dạng THANHGO.OUT
– Dòng thứ nhất ghi độ dài ngắn duy nhất tìm được.
– bên trên mỗi chiếc ghi số hiệu những mẩu gỗ dùng làm ghép thành thanh gỗ đó.
Áp dụng việc chia team 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 lớn n doif l0 bởi lan nguoc sở hữu c tim cac phan tu ta cong vaobeginluu