Ít nhất 1 tổ hợp sao cho tổng bằng giá trị cho trước (2 người xem)

[kuldokk]

Chào các Chị, các Anh trong GPE,

Em có 1 vấn đề khi cân bằng Cash flow thế này. Trong file Excel đính kèm ở cột A (A4:A417) có chứa 1 loạt các giá trị. Làm thế nào để tìm được 01 tập hợp các giá trị ở cột A này mà tổng bằng giá trị ở ô D2.

Em đã thử sử dụng add-in Solver, SumMatchcủa Excel và tham khảo

Ðề tài: Tìm các con số có tổng bằng 1 con số cho trước @Hong.Van

nhưng không cho kết quả khả quan.

Mong nhận được sự giúp đỡ của mọi người. Em xin cảm ơn trước!

 

[Hong.Van]

Chào các Chị, các Anh trong GPE,

Em có 1 vấn đề khi cân bằng Cash flow thế này. Trong file Excel đính kèm ở cột A (A4:A417) có chứa 1 loạt các giá trị. Làm thế nào để tìm được 01 tập hợp các giá trị ở cột A này mà tổng bằng giá trị ở ô D2.

Em đã thử sử dụng add-in Solver, SumMatchcủa Excel và tham khảo code VBA ở trang này

http://www.tushar-mehta.com/excel/templates/match_values/

nhưng không cho kết quả khả quan.

Mong nhận được sự giúp đỡ của mọi người. Em xin cảm ơn trước!

Bạn đọc Ðề tài: Tìm các con số có tổng bằng 1 con số cho trước

 

[kuldokk]

Bạn đọc Ðề tài: Tìm các con số có tổng bằng 1 con số cho trước

Cảm ơn bạn, mình đã xem qua bài này trước khi post bài ... không áp dụng được.

 

[Hong.Van]

Cảm ơn bạn, mình đã xem qua bài này trước khi post bài ... không áp dụng được.

Tôn nghỉ kg fải kg áp dụng được, mà có thể do dãy số dò tìm của bạn QUÁ NHIẾU

 

[kuldokk]

Tôn nghỉ kg fải kg áp dụng được, mà có thể do dãy số dò tìm của bạn QUÁ NHIẾU

1. Cảm ơn bạn đã quan tâm đến chủ đề.
2. Vấn đề của mình ở quy mô khác, trong đề tài bạn chỉ ra, chỉ có 10 số thôi và 10 số đó đều là số nguyên dương.
3. Mình biết đọc và cũng biết là dãy số dài, khi giải pháp không xử lý được vì input nhiều thì theo mình đúng là không áp dụng được.

 

[Hong.Van]

1. Cảm ơn bạn đã quan tâm đến chủ đề.
2. Vấn đề của mình ở quy mô khác, trong đề tài bạn chỉ ra, chỉ có 10 số thôi và 10 số đó đều là số nguyên dương.
3. Mình biết đọc và cũng biết là dãy số dài, khi giải pháp không xử lý được vì input nhiều thì theo mình đúng là không áp dụng được.

Cái dòng màu đỏ là kg đúng nha! Bạn thử chạy code ở file đính kèm thử

 

[kuldokk]

Cái dòng màu đỏ là kg đúng nha! Bạn thử chạy code ở file đính kèm thử

1. Phân tích file

dòng đỏ mình viết ra dựa trên file excel ở đề tài đó và dòng đỏ đó đúng là có 10 số, 10 số đều là số nguyên dương.
Nếu so dòng đỏ ấy với file test của bạn thì đúng là dòng đỏ không đúng.

2. Vấn đề ở đây là vấn đề "Sum of Subset", nếu google + biết 1 chút tiếng anh, các bạn có thể dễ dàng đọc được đây là 1 vấn đề trong khoa học máy tính. Cách giải đơn giản và không hiệu quả nhất là liệt kê ra tất cả các tập con của list số và tính tổng rồi so sánh với kết quả đề ra. Và tất nhiên cách làm này không hiệu quả. Để chỉ ra sự không hiệu quả này chúng ta lấy 1 list có 20 số chẳng hạn, số lượng tập con của 1 list có 20 số là 2^20 = 1048576 và để tìm ra kết quả chúng ta phải so sánh hơn 1 triệu kết quả này.

3. Phân tích Function của bạn post trong file:

   For j = PhanTu To n - k + SoDem 'Sua cho nay se giam duoc 1/2 so lan goi sub nay
      KQi(SoDem, 1) = MgNguon(j, 1)
      Main k, KQi, CongDon + KQi(SoDem, 1), j + 1, SoDem + 1
   Next j

Đệ quy, trong vòng for của hàm Main và trong sub kiemtra() lại có 1 vòng for nữa cho 20 phần tử của dãy. Tóm lại chúng ta có 1 số vòng for và đệ quy của hàm Main().

Nếu~----> với code này thì chỉ cần tăng lên 30 số thôi là chạy mất kha khá thời gian rồi. Rất là không hiệu quả. Nếu có thời gian, bạn hãy tham khảo file mình với up lên (mình thấy bạn cũng có hứng thú với chủ đề này), chạy tốt với dãy 70 số trở xuống, mất khoảng 4s.