Thuật toán tính tổng Ax+By+...+Cz = hằng số cho trước

[tvst11246]

Dear các anh chị!
Em đang gặp bài toán như sau:
Ax+By+...+Cz = Constant
Trong đó x, y,...,z là những số nguyên và được lấy ngẫu nhiên từ trong dãy từ 1-9
A, B,...C, Constan là những số cho trước
Xác đinh x, y,...z.
Ví dụ như em đính kèm.
Các anh chị giúp em với.

 

[VMH0307]

Dear các anh chị!
Em đang gặp bài toán như sau:
Ax+By+...+Cz = Constant
Trong đó x, y,...,z là những số nguyên và được lấy ngẫu nhiên từ trong dãy từ 1-9
A, B,...C, Constan là những số cho trước
Xác đinh x, y,...z.
Ví dụ như em đính kèm.
Các anh chị giúp em với.

Bài toán này hoàn toàn có thể sử dụng Solver để giải quyết. Bạn tỉm hiểu trên diễn đàn có nhiều lắm đó.

 

[tvst11246]

Bài toán này hoàn toàn có thể sử dụng Solver để giải quyết. Bạn tỉm hiểu trên diễn đàn có nhiều lắm đó.

Em đọc về Solver rồi, nhưng cái đó chỉ dùng để tìm hàm tối ưu thôi.

 

[hungpecc1]

Em đọc về Solver rồi, nhưng cái đó chỉ dùng để tìm hàm tối ưu thôi.

ý bạn là muốn liệt kê tất cả các trường hợp có thể xảy ra: trong các trương hợp liệt kệ ra, trường hợp nào thoả mãn điều kiện tổng thì chọn :???
==> ở đây mình thử dùng thuật toán đệ quy quay lui , nội dung của nó như sau :
Giả thiết cấu hình cần tìm được mô tả bằng một bộ gồm n thành phần x1, x2, …, xn. Giả sử đã xác định được i-1 thành phần x1, x2, …, xi-1 ta xác định thành phần xi bằng cách duyệt tất cả các khả năng có thể đề cử cho nó (đánh số các khả năng từ 1 đến ni). Với mỗi khả năng j, kiểm tra xem j có chấp nhận được hay không. Xẩy ra hai trường hợp:

• ØNếu chấp nhận j thì xác định xi theo j, sau đó nếu i=n thì ta được một cấu hình, còn trái lại ta tiến hành việc xác định xi+1.
• ØNếu thử tất cả các khả năng mà không có khả năng nào được chấp nhận thì quay lại bước trước để xác định lại xi-1.

==> nếu áp cách này nếu số lượng phần tử mảng lớn--> sẽ mất rất nhiều thời gian (<-- để tìm được thuật toán tối ưu, có lẽ phải nhờ đến các cao thủ như anh Switom, ndu, Huuthang,VetMini,Vodoi2x, Hoàng T Nghĩa....)

*mình ví dụ 1 đoạn code như sau :
**Cho một mảng { 1 ,2, 3, 4} , mỗi giá trị trong mảng sẽ nhân với một số tự nhiên từ Xi từ 1--> 8 :
-->Yêu cầu: Liệt kê tất cả các trường hợp : 1.Xi + 2Xi +3Xi+4Xi , tìm trường hợp thỏa mãn :1.Xi + 2Xi +3Xi+4Xi =66

Option Explicit
Public Arr, Result,str$
'----------------------------------------------------
Sub Try(ByVal i As Long)
    Dim item
        For Each item In Array(1, 2, 3, 4, 5, 6, 7, 8)
            Result(i) = Arr(i) * item
            If i = UBound(Arr) Then
                    Check Result
            Else
                Try i + 1
            End If
            
        Next
End Sub
'------------------------------------------------------
Sub Check(Arr)
Dim i&, tong#
    For i = LBound(Arr) To UBound(Arr)
        tong = tong + Arr(i)
    Next
        If tong = 66 Then
            str=str & Join(Arr, "+") & "=" & tong & chr(10)
        Else
            Debug.Print Join(Arr, "+") & "=" & tong
        End If
End Sub
'--------------------------------------------------------
Sub main()
    Dim tmpArr
        Arr = Array(1, 2, 3, 4)
        ReDim Result(LBound(Arr) To UBound(Arr))
        Try 0
        msgbox str
End Sub

 

[tvst11246]

Cái của anh @hungpecc1 không chạy được và có vẻ hơi loằng ngoằng. Tuy nhiên em thử 1 đoạn code macro như sau, với 3 bộ số. Máy chạy ngon, nhưng làm đến 15 phát thì đơ luôn.

Sub Macro1()
Dim i1, i2, i3, So_Bo_So_tim_duoc, Cell_next As Integer
Const A = 300
Const B = 200
Const C = 200
Const Total = 1200
So_Bo_So_tim_duoc = 0
For i1 = 1 To 8
For i2 = 1 To 8
For i3 = 1 To 8
If A * i1 + B * i2 + C * i3 = Total Then
Cells(Cell_next, 5) = " & i1 & "-" & i2 & "-" & i3
So_Bo_So_tim_duoc = So_Bo_So_tim_duoc + 1
Cell_next = Cell_next + 1
End If
Next
Next
Next

MsgBox "So bo so tim duoc la: " & So_Bo_So_tim_duoc
End Sub

 

[hungpecc1]

Cái của anh @hungpecc1 không chạy được và có vẻ hơi loằng ngoằng. Tuy nhiên em thử 1 đoạn code macro như sau, với 3 bộ số. Máy chạy ngon, nhưng làm đến 15 phát thì đơ luôn.

Sub Macro1()
Dim i1, i2, i3, So_Bo_So_tim_duoc, Cell_next As Integer
Const A = 300
Const B = 200
Const C = 200
Const Total = 1200
So_Bo_So_tim_duoc = 0
For i1 = 1 To 8
For i2 = 1 To 8
For i3 = 1 To 8
If A * i1 + B * i2 + C * i3 = Total Then
Cells(Cell_next, 5) = " & i1 & "-" & i2 & "-" & i3
So_Bo_So_tim_duoc = So_Bo_So_tim_duoc + 1
Cell_next = Cell_next + 1
End If
Next
Next
Next

MsgBox "So bo so tim duoc la: " & So_Bo_So_tim_duoc
End Sub

code bạn làm về mặt logic cũng gần như code của mình, có điều nếu bộ 20 số --> bạn phải viết 20 vòng for lồng vào nhau ??, nếu n bộ số --> bạn phải viết n vòng for???
==> bài toán liệt kê tổ hợp là một dạng toán khó, nếu không có thêm điều kiện biên ( để hạn chế số lượng, cũng như loại bỏ những điều kiện không thỏa mãn ) --> ....
vdu : với bộ 3 {i1,i2,i3} trong đó mỗi số Ij được chọn từ {1-8} --> sẽ có tất cả 8^3 = 512 bộ 3 số thoản mãn , nếu bộ 15 số sẽ là : 8^15 = 3518E13 ( rất lớn phải không ).
Nhưng vì bạn có điều kiện biên là tổng các bộ số = A --> bạn có thể hạn chế vòng lặp bằng cách tính tổng ,kiểm tra từng thành phần mỗi vòng lặp, nếu tổng > A -->exit For
* Trường hợp xấu nhất độ phức tạp bài toán vẫn là 8^n

p/s : code ở trên mình viết, bạn phải chạy Sub Main()

 

[tvst11246]

code bạn làm về mặt logic cũng gần như code của mình, có điều nếu bộ 20 số --> bạn phải viết 20 vòng for lồng vào nhau ??, nếu n bộ số --> bạn phải viết n vòng for???
==> bài toán liệt kê tổ hợp là một dạng toán khó, nếu không có thêm điều kiện biên ( để hạn chế số lượng, cũng như loại bỏ những điều kiện không thỏa mãn ) --> ....
vdu : với bộ 3 {i1,i2,i3} trong đó mỗi số Ij được chọn từ {1-8} --> sẽ có tất cả 8^3 = 512 bộ 3 số thoản mãn , nếu bộ 15 số sẽ là : 8^15 = 3518E13 ( rất lớn phải không ).
Nhưng vì bạn có điều kiện biên là tổng các bộ số = A --> bạn có thể hạn chế vòng lặp bằng cách tính tổng ,kiểm tra từng thành phần mỗi vòng lặp, nếu tổng > A -->exit For
* Trường hợp xấu nhất độ phức tạp bài toán vẫn là 8^n

p/s : code ở trên mình viết, bạn phải chạy Sub Main()

Cảm ơn anh! Em đang nghĩ tiếp về vài giới hạn để lược bỏ bớt các điều kiện.