Home / Nhà Đất / bài toán chia kẹo

BÀI TOÁN CHIA KẸO

admin - 05/03/2022 546

Bài tân oán chia kẹo c++ là 1 trong dạng toán thù nổi bật, bài bác toán thù này có phương thức giải đặc trưng, tứ tưởng của nó có thể được vận dụng để giải mang đến không hề ít bài bác tân oán khác vào Tin học tập . Nó còn có tên điện thoại tư vấn là Number Partitioning, không có thuật toán tối ưu nhằm giải. Sau đấy là đều thuật tân oán từ bỏ dễ dàng đến khó để giải quyết và xử lý bài tập này cùng với timhome.vn nhé.

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

Video lí giải bài tân oán phân tách kẹo pascal

Thuật toán thù phân chia kẹo

Một bài xích tân oán được Hotline là 1 bàitân oán tốt giả dụ nó là 1 trong những bài toán thù cạnh tranh cùng tất cả giải mã rất dị. Bài toán thù “Chia kẹo” là một trong những dẫn chứng mang lại điềuđó. Bài tân oán này có phương thức giải quan trọng, tứ tưởng của nó có thể được ápdụng để giải đến rất nhiều bài tân oán không giống trong Tin học tập. Các chúng ta có thể thamkhảo nội dung bài viết “Thuật toán thù phân chia kẹo cùng vận dụng giải lớp bài tân oán chianhóm” của người sáng tác Lã Thành Công bên trên số báo mon 1/2001. Sauđây tôi xin trình diễn cách thức giải bài tân oán này cùng ứng dụng thuật toánvào vấn đề giải những bài toán thù tin không giống.

Nhắc lại bài xích tân oán chia kẹo

Có N gói kẹo, gói thứ i tất cả Aimẫu kẹo. Không được tách 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 làm thế nào cho độ chênh lệch số kẹo giữa nhì gói là tối thiểu.

Dữ liệu vào vào tệp tin “chiakeo.inp” bao gồm dạng :

– Dòng trước tiên là số N(N

– Dòng máy hai là N số Ai(i=1, 2,.., N; Ai

Kết quả ra tệp tin “chiakeo dán giấy.out” gồm dạng:

– Dòng đầu là độ chênh lệchbé dại nhất giữa nhì phần hoàn toàn có thể được.

– Dòng hai là một trong dãy N số,nếu như đam mê =1 thì gói máy i trực thuộc phần 1, nếu say mê =2 thì góilắp thêm i nằm trong phần 2

Thuật toán:

Với một số trong những M bất kể, nếu như ta biếtđược gồm lâu dài một giải pháp lựa chọn các gói kẹo nhằm toàn bô kẹo của các gói được chọnbởi đúng M không, thì bài tân oán được giải đã quyết. Vì đơn giản dễ dàng là ta chỉ cầnlựa chọn số M làm thế nào để cho M ngay sát với

Ai/2tuyệt nhất (cùng với i =1,2,..,N). Sau kia xếp những gói kẹo để tổng bởi M vào phần một,phần lắp thêm hai sẽ bao gồm những gói kẹo sót lại. Để đánh giá được điều bên trên ta sẽ xâydựng toàn bộ các tổng có thể có của N gói kẹo bằng cách: ban đầu chưa xuất hiện tổngnào được hiện ra. Làm theo lần lượt cùng với các gói kẹo từ là 1 mang lại N, cùng với gói kẹo máy i,ta kiểm tra coi bây giờ có các tổng như thế nào đã được sinh ra, đưa sử các tổng đó làx1, x2,.., xt vậy thì cho tới bước này sẽ có được thểsinh ra các tổng x1, x2,.., xt và Aicùng x1+Ai,x2+Ai,..,xt+Ai.Với N gói kẹo, mà từng gói có không quá 100 dòng kẹo vậy tổng số kẹo ko vượtthừa N*100 0 bởi vì lan nguoc với c tyên ổn cac phan tu ta cong vao de duoc mbegins>:=1;phan tu nao da mang lại vao tong thi danh dau la 1m:=m-a>;end;--------ghi ket qua-----------assign(f,"chiakeo dán giấy.out");rewrite(f);writeln(f,sum-2*tu); sum-2*m la vùng cach giua 2 phanfor i:=1 lớn n vày write(f,s," ");close(f);END.
Bài toán phân chia kẹo quy hướng động
Ý tưởng: gọi T là toàn bô kẹo của N gói. Chúng ta bắt buộc tìm kiếm số S lớn nhất thỏa mãn: S _ Hướng dẫn giải QHĐ: + Giống nhỏng bài xích chào bán hoa, mà lại không giống sinh hoạt hàm tính quý hiếm. Việc tạo thành bảng QHĐ: Chỉ nên ưng chuẩn n túi kẹo và Tổng/2 kẹo. tài liệu vẫn lưu giữ vào 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 phụ thuộc vào điều kiện: KHÔNG LẤY túi máy i khi còn chỉ khi (L > L> + A) Hoặc (L> +A L> + A tức là giá trị của khi không rước túi i ( L) to hơn Lúc rước nhiều loại i (L> + A). L> +A Var i: integer; Begin i:=n; While i 0 vì chưng Begin If LL then Begin Write(fo,i, ‘ ‘); m:=m-a; End; i:= i-1; End; end;

Ứng dụng giải bài xích toán thù CÁC THANH GỖ (đề Lâm Đồng)

Trong một buổi cắm trại của lớp, bạn An download N thanh khô gỗ có độ dài mỗi tkhô nóng là L. Khi cắm trại, các người mua hàng của An cưa các tkhô hanh mộc ra một phương pháp bỗng dưng (có độ lâu năm là số nguyên).

Về sau các người mua gồm ý muốn gắn các mẩu bé để khôi phục lại những tkhô hanh mộc ban sơ mà lại lại không để ý độ nhiều năm L. Họ đang quyết định nối lại các tkhô giòn mộc sao cho chúng bao gồm độ dài đều 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 giúp họ chọn cách nối làm thế nào cho chúng tất cả độ dài hệt nhau cùng càng ngắn càng tuyệt.

Dữ liệu vào: cho trong tệp tin văn bản THANHGO.INP:

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

– N cái tiếp theo mỗi dòng ghi số nguim Li (1 £ Li £ 100, 1 £ i £ N) biểu lộ độ dài của mẩu mộc trang bị i.

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

– Dòng trước tiên ghi độ lâu năm nđính tốt nhất tìm kiế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 từng dòng ghi số hiệu những mẩu gỗ dùng để ghnghiền thành tkhô cứng mộc đó.

Áp dụng bài tân oán phân tách team trên nhằm giải:

Program thanh_go;Var dem,k,n,i,j,L1,LL,T: word;luu,L,lvt,không lấy phí,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 khổng lồ n dobeginread(f,L);lvt:=i;T:=T+L;end;close(f);s:=L;end;procedure sapxep;beginfor i:=1 khổng lồ n-1 dofor j:=i+1 lớn n doif l0 vày lan nguoc sở hữu c tlặng cac phan tu ta cong vaobeginluu>:=dem;phan tu nao domain authority mang lại vao tong thi danh daufree>:=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 khổng lồ k dobeginfor j:=1 khổng lồ n doif luu=i then write(f,lvt," ");writeln(f);end;close(f);end;--------chuong trinh chinh-----------begindoc;sapxep;For L1:=LL khổng lồ T doif T mod L1 =0 thenbegink:=T div L1; dem:=0;For i:=1 khổng lồ n bởi vì free:=0;for i:=1 khổng lồ n bởi vì luu:=0;repeatktra(L1);until (dem=k)or(ktra(L1)=false);if dem=k thenbegininkq;break; neu tyên ổn duoc ket qua thi thoat vong lap for kiem traend;end;kết thúc.