Cần giúp đỡ tìm phương pháp tối ưu

[lưukeni]

	A	Code	B	Code
1	200		415	abc
2	100		520	def
3	300		610	ghj
4	240		55	klo
5	255
6	55
7	320
8	25
9	50
10	55
Tổng	1600​		1600​
Điền giá trị code của B vào A sao cho khớp số tiền

Các anh chị cho em hỏi có cách nào lập được công thức hay bài toán nào giải quyết vấn đề này không ạ, em có ví dụ trên yêu cầu điền code của cột B vào cột A, biết là trong 1 dãy của A có những số cộng lại sẽ bằng dòng 1 của B và tương tự dòng 2 dòng 3. Do đây là ví dụ nên em lượt bớt cho đơn giản chứ thực tế A lên đến 3k dòng và B có thể hơn 2k dòng nhưng số tổng bằng A = B và chắc chắn là những giá trị của A cộng lại chắc chắn bằng 1 giá trị bên B ạ.

 

[HieuCD]

	A	Code	B	Code
1	200		415	abc
2	100		520	def
3	300		610	ghj
4	240		55	klo
5	255
6	55
7	320
8	25
9	50
10	55
Tổng	1600​		1600​
Điền giá trị code của B vào A sao cho khớp số tiền

Các anh chị cho em hỏi có cách nào lập được công thức hay bài toán nào giải quyết vấn đề này không ạ, em có ví dụ trên yêu cầu điền code của cột B vào cột A, biết là trong 1 dãy của A có những số cộng lại sẽ bằng dòng 1 của B và tương tự dòng 2 dòng 3. Do đây là ví dụ nên em lượt bớt cho đơn giản chứ thực tế A lên đến 3k dòng và B có thể hơn 2k dòng nhưng số tổng bằng A = B và chắc chắn là những giá trị của A cộng lại chắc chắn bằng 1 giá trị bên B ạ.

Dùng thuật toán vét cạn sẽ tìm được, nhưng với lượng dữ liệu lớn code chạy có thể mất vài năm(1), cần phải thêm nhiều liên kết với dữ liệu thực tế mới tăng tốc được code
(1) Chỉ ước tính không dám thử

 

[SA_DQ]

Trong ví dụ của #1 ta có:
(1) Tổng của cột 'B' là 1600
(2) Số lượng dòng (hàng) của cột 'A' là 10
Bước 1: Lấy (1) đem chia cho (2) (1.600/10)
- Ta được 160
Bước 2 Tạo vòng lặp duyệt các dòng cột 'A' trừ đi 1 & rãi số 160 ± Alf (Alf là số ngẫu nhiên nào đó không lớn lắm (ví dụ ≤ 13))
Bước 3: Dòng cuối: Giàu út ăn, nghèo út chịu!

Chúc bạn thành công & vui cả ngày!

 

[VetMini]

Dùng thuật toán vét cạn sẽ tìm được, nhưng với lượng dữ liệu lớn code chạy có thể mất vài năm(1), cần phải thêm nhiều liên kết với dữ liệu thực tế mới tăng tốc được code
(1) Chỉ ước tính không dám thử

Vét khó lắm.
Ví dụ tôi có B1+B2+B3 = A1, đồng thời B5+B6+B7+B8 cũng = A1.
Tôi chọn nhóm B1B2B3. Sau đó đến A4 không tìm được, vì B nào đó đã nằm trong A1. Thế là tôi lại phải xả A1 ra, tìm lại.

Tôi e rằng phải dùng đến các thuật toán tìm đường đi.

 

[cantl]

Em thấy bài này có nhiều đáp án quá.
415 = Tổng n số (1) . Với n bao la
520 = Tổng n số (2) . Với n bao la
610 = Tổng n số (3) . Với n bao la
55 = Tổng n số (4) . Với n bao la
1600 = (1) + (2) + (3) + (4)

 

[anhtuanle123]

theo ngu ý của e thì bài này cùng hệ với bài cắt vật tư, cột B là các thanh dài với chiều dài khác nhau, cột A là các thanh ngắn với chiều dài khác nhau (xin tạm gọi các số đơn vị là thanh), khó là với vô số chiều dài khác nhau thì khó đưa về dạng ma trận tuyến tính để tính tối ưu được (theo hiểu bít hiện tại), chỉ còn cách vét cạn,
có 1 vài ưu điểm là tác giả đề bài chắc chắn các thanh con xếp lại sẽ vừa khít các thanh lớn, và số lượng thanh lớn được biết trước cố định, nhưng với số lượng thanh nhỏ 3k và thanh lớn 2k chắc vét đến mùa quýt để sắp xếp cho khít được @@

 

[VetMini]

...
có 1 vài ưu điểm là tác giả đề bài chắc chắn các thanh con xếp lại sẽ vừa khít các thanh lớn, và số lượng thanh lớn được biết trước cố định, nhưng với số lượng thanh nhỏ 3k và thanh lớn 2k chắc vét đến mùa quýt để sắp xếp cho khít được @@

Số lượng nhiều chỉ là một yếu tố. Nếu chỉ phải vét cạn 1 lượt thì cuối cùng cũng ra.

Vấn đề tôi đã nêu ở trên, các số lớn có khả năng nhiều cách xếp vào, và có thể nó cứ phải bị chọn lại vì phải nhường cho các số ít cách hơn.
Ví dụ:
A1 = 550, vét được 200, 350
A2 = 355, không tìm được số nào. Nhưng có 5, nếu không lấy được 350 của A1 thì không còn cách nào khác.
Tạm giải quyết:
A2 = 350 + 5
A1 vét lại lượt khác, được 100, 170, 280

Đó là ý chính khi tôi nói vét cạn 1 lượt, nhiều lượt.

 

[HieuCD]

Vét khó lắm.
Ví dụ tôi có B1+B2+B3 = A1, đồng thời B5+B6+B7+B8 cũng = A1.
Tôi chọn nhóm B1B2B3. Sau đó đến A4 không tìm được, vì B nào đó đã nằm trong A1. Thế là tôi lại phải xả A1 ra, tìm lại.

A1 tìm được N phương án các tổng các Bi khác nhau, xét từng phương án A1 để tìm các phương án của A2 ...
Phải xét từng khả năng nên phải tính đi tính lại nhiều lần sẽ tốn rất nhiều thời gian, máy tính thường không thể xử lý được