BÀI TOÁN TÌM GIÁ USD VÀ TÌM LƯỢNG KG - NHỜ ANH/CHỊ GIÚP ĐỠ (1 người xem)

Liên hệ QC

Người dùng đang xem chủ đề này

Tôi tuân thủ nội quy khi đăng bài

khuongnguyencm69

Thành viên mới
Tham gia
7/6/16
Bài viết
31
Được thích
5
Em có bài toán như sau:
TỔNG TIỀN = 190415 USD

TỔNG KG = 18700 KG

KG1 NẰM TRONG KHOẢNG 9500 KG ĐẾN 9500 KG

KG2 NẰM TRONG KHOẢNG 700 KG ĐẾN 800 KG

KG3 NẰM TRONG KHOẢNG 8400 KG ĐẾN 8500 KG

GIA1 NẰM TRONG KHOẢNG 10 USD ĐẾN 11 USD

GIA2 NẰM TRONG KHOẢNG 10 USD ĐẾN 11 USD

GIA3 NẰM TRONG KHOẢNG 9 USD ĐẾN 10 USD

TÌM: GIA1, GIA2, GIA3

TÌM: KG1, KG2, KG3

SAU CHO: GIA1 X KG1 + GIA2 X KG2 + GIA3 X KG3 = 190415

TỔNG KG: KG1 + KG2 + KG3 = 18700

KG2 + KG3 = 9200

KG1, KG2, KG3 CHIA HẾT CHO 10

BƯỚC NHẢY STEP GIÁ 0.001

Em có dùng thuật toán Bruteforce nhưng vòng lặp lớn và máy chạy không nổi, anh chị có cách nào hay hơn giúp em ạ!
EM CÓ LƯỢNG TÍNH BẰNG TAY THOẢ MÃN, NẾU CÁC CẶP LƯỢNG VÀ GIÁ ĐẠT KHOẢNG 10 - 15 CẶP THÌ DỪNG CHƯƠNG TRÌNH Ạ!

99,930.500 10.519
7,210.000 10.3
83,274.500 9.797
Bài đã được tự động gộp:

KG1, KG2, KG3 LẦN LƯỢT

9500
700
8,500
 
Lần chỉnh sửa cuối:
Em có dùng thuật toán Bruteforce nhưng vòng lặp lớn và máy chạy không nổi, anh chị có cách nào hay hơn giúp em ạ!
EM CÓ LƯỢNG TÍNH BẰNG TAY THOẢ MÃN, NẾU CÁC CẶP LƯỢNG VÀ GIÁ ĐẠT KHOẢNG 10 - 15 CẶP THÌ DỪNG CHƯƠNG TRÌNH Ạ!
Bạn có thể chia sẻ code của bạn dùng thuật toán Bruteforce lên diễn đàn này không?
 
Upvote 0
Mình hỏi Copilot nè:
PHP:
Sub BruteForceSearch()
    Dim totalMoney As Long
    Dim totalKg As Long
    Dim kg1 As Long, kg2 As Long, kg3 As Long
    Dim gia1 As Long, gia2 As Long, gia3 As Long
    Dim i As Long, j As Long, k As Long
    Dim l As Long, m As Long, n As Long

    ' Define the constraints   '
    totalMoney = 190415
    totalKg = 18700

    ' Try all possible combinations   '
    For kg1 = 9500 To 9500 Step 10
        For kg2 = 700 To 800 Step 10
            For kg3 = 8400 To 8500 Step 10
                If kg2 + kg3 <> 9200 Then
                    GoTo NextIteration1
                End If
              
                For gia1 = 10 To 11
                    For gia2 = 10 To 11
                        For gia3 = 9 To 10
                            If (gia1 * kg1 + gia2 * kg2 + gia3 * kg3 = totalMoney) And _
                               (kg1 + kg2 + kg3 = totalKg) Then
                                Debug.Print "KG1 = " & kg1 & ", KG2 = " & kg2 & ", KG3 = " & kg3
                                Debug.Print "GIA1 = " & gia1 & ", GIA2 = " & gia2 & ", GIA3 = " & gia3
                            End If
NextIteration1:
                        Next gia3
                    Next gia2
                Next gia1
              
            Next kg3
        Next kg2
    Next kg1
End Sub

Chủ bài đăng thử đo thời gian chương trình này của Copilot xem có khả dĩ hơn của bạn hay không?
 
Upvote 0
Mình hỏi Copilot nè:
...

Chủ bài đăng thử đo thời gian chương trình này của Copilot xem có khả dĩ hơn của bạn hay không?
So sánh khập khễnh. Bài của Copilot không có điều kiện bước nhảy giá mà giả sử chúng là 1

Vả lại, bài giải của Copilot không theo đúng tinh thần brute force.
Bài toán brute force phải bao gồm cả trường hợp không có lời giải chính xác thì lời giải gần nhất có chấp nhận được chăng?
 
Upvote 0
code này nè chạy chậm lắm, mình nghĩ sẽ dùng python thì ngôn ngữ mạnh hơn.
mình tính ra vòng lặp như vậy gần cả tỷ phép tính, nên máy bị treo, hix.
mình có tìm hiểu thuật toán quy hoạch động nhưng nó khá khó nhai và mình ko đủ trình để hiểu nó, do giới hạn về hiểu biết và thiên phú toán ở độ trung bình, hix
Sub FindWeightAndPrice()
Dim KG1 As Long, KG2 As Long, KG3 As Long
Dim GIA1 As Double, GIA2 As Double, GIA3 As Double
Dim totalPrice As Double
Dim totalKG As Long
Dim found As Boolean

totalPrice = 190415
totalKG = 18700
found = False

' Vòng lặp qua các giá trị của GIA1, GIA2, GIA3
For GIA1 = 10 To 11 Step 0.001
For GIA2 = 10 To 11 Step 0.001
For GIA3 = 9 To 10 Step 0.001
' Vòng lặp qua các giá trị của KG1, KG2, KG3
For KG1 = 9500 To 9500 Step 10
For KG2 = 700 To 800 Step 10
For KG3 = 8400 To 8500 Step 10
' Kiểm tra các điều kiện
If (KG1 + KG2 + KG3 = totalKG) And _
(KG2 + KG3 = 9200) And _
(GIA1 * KG1 + GIA2 * KG2 + GIA3 * KG3 = totalPrice) Then
' Nếu thỏa mãn các điều kiện, in ra kết quả
Debug.Print "KG1: " & KG1 & ", KG2: " & KG2 & ", KG3: " & KG3
Debug.Print "GIA1: " & Format(GIA1, "0.000") & ", GIA2: " & Format(GIA2, "0.000") & ", GIA3: " & Format(GIA3, "0.000")
found = True
End If
Next KG3
Next KG2
Next KG1
Next GIA3
Next GIA2
Next GIA1

If Not found Then
Debug.Print "Không tìm thấy giá trị thỏa mãn."
End If
End Sub
 
Upvote 0
Em có bài toán như sau:
TỔNG TIỀN = 190415 USD

TỔNG KG = 18700 KG

KG1 NẰM TRONG KHOẢNG 9500 KG ĐẾN 9500 KG

KG2 NẰM TRONG KHOẢNG 700 KG ĐẾN 800 KG

KG3 NẰM TRONG KHOẢNG 8400 KG ĐẾN 8500 KG

GIA1 NẰM TRONG KHOẢNG 10 USD ĐẾN 11 USD

GIA2 NẰM TRONG KHOẢNG 10 USD ĐẾN 11 USD

GIA3 NẰM TRONG KHOẢNG 9 USD ĐẾN 10 USD

TÌM: GIA1, GIA2, GIA3

TÌM: KG1, KG2, KG3

SAU CHO: GIA1 X KG1 + GIA2 X KG2 + GIA3 X KG3 = 190415

TỔNG KG: KG1 + KG2 + KG3 = 18700

KG2 + KG3 = 9200

KG1, KG2, KG3 CHIA HẾT CHO 10

BƯỚC NHẢY STEP GIÁ 0.001

Em có dùng thuật toán Bruteforce nhưng vòng lặp lớn và máy chạy không nổi, anh chị có cách nào hay hơn giúp em ạ!
EM CÓ LƯỢNG TÍNH BẰNG TAY THOẢ MÃN, NẾU CÁC CẶP LƯỢNG VÀ GIÁ ĐẠT KHOẢNG 10 - 15 CẶP THÌ DỪNG CHƯƠNG TRÌNH Ạ!

99,930.50010.519
7,210.00010.3
83,274.500 9.797
Bài đã được tự động gộp:

KG1, KG2, KG3 LẦN LƯỢT

9500
700
8,500
Thử 1 cách dùng solver trong file đính kèm.
Nhập B2:C4 = 1 rồi chạy solver
Kết quả thành tiền = 190512, có sai lệch với yêu cầu 190415. Các điều kiện khác đều thỏa mãn

Bài này vba có lẽ vẫn có thể xử lý được
 

File đính kèm

Upvote 0
SAU CHO: GIA1 X KG1 + GIA2 X KG2 + GIA3 X KG3 = 190415

TỔNG KG: KG1 + KG2 + KG3 = 18700 (1)

KG2 + KG3 = 9200 (2)

KG1, KG2, KG3 CHIA HẾT CHO 10

BƯỚC NHẢY STEP GIÁ 0.001
1. Bỏ vòng lặp KG1, vì theo (1) và (2), KG1 luôn bằng: 18700 - 9200 = 9500

2. Bỏ vòng lặp KG3, vì theo (2), KG3 = 9200-KG2

Hy vọng sau khi bỏ 2 vòng lặp, code sẽ chạy nhanh hơn.
 
Upvote 0
Em có bài toán như sau:
TỔNG TIỀN = 190415 USD

TỔNG KG = 18700 KG

KG1 NẰM TRONG KHOẢNG 9500 KG ĐẾN 9500 KG

KG2 NẰM TRONG KHOẢNG 700 KG ĐẾN 800 KG

KG3 NẰM TRONG KHOẢNG 8400 KG ĐẾN 8500 KG

GIA1 NẰM TRONG KHOẢNG 10 USD ĐẾN 11 USD

GIA2 NẰM TRONG KHOẢNG 10 USD ĐẾN 11 USD

GIA3 NẰM TRONG KHOẢNG 9 USD ĐẾN 10 USD

TÌM: GIA1, GIA2, GIA3

TÌM: KG1, KG2, KG3

SAU CHO: GIA1 X KG1 + GIA2 X KG2 + GIA3 X KG3 = 190415

TỔNG KG: KG1 + KG2 + KG3 = 18700

KG2 + KG3 = 9200

KG1, KG2, KG3 CHIA HẾT CHO 10

BƯỚC NHẢY STEP GIÁ 0.001

Em có dùng thuật toán Bruteforce nhưng vòng lặp lớn và máy chạy không nổi, anh chị có cách nào hay hơn giúp em ạ!
EM CÓ LƯỢNG TÍNH BẰNG TAY THOẢ MÃN, NẾU CÁC CẶP LƯỢNG VÀ GIÁ ĐẠT KHOẢNG 10 - 15 CẶP THÌ DỪNG CHƯƠNG TRÌNH Ạ!

99,930.50010.519
7,210.00010.3
83,274.500 9.797
Bài đã được tự động gộp:

KG1, KG2, KG3 LẦN LƯỢT

9500
700
8,500
1738986510022.png
Mình thử chạy Solver ra kết quả này.
 
Lần chỉnh sửa cuối:
Upvote 0
code này nè chạy chậm lắm, mình nghĩ sẽ dùng python thì ngôn ngữ mạnh hơn.
...
Brute force thì dùng C. Bái thần với bái thánh chỉ trong trường hợp có thể dùng được các phép tính có sẵn trong thư viện (mà các thư viện này hầu hết được viết bằng C)
Vả lại, code trên được viết bởi người không có căn bản lập trình số thực. Khi tính toán số thực có thập phân thì phải chấp nhận sai số.
Hai biểu thức so sánh ít khi bằng y nhau. Theo luật lập trình số thực thì phải chấp nhận:
ABS((biểu thức A) - (biểu thức B)) <= Ép si lon
 
Upvote 0
Em có bài toán như sau:
TỔNG TIỀN = 190415 USD

TỔNG KG = 18700 KG

KG1 NẰM TRONG KHOẢNG 9500 KG ĐẾN 9500 KG

KG2 NẰM TRONG KHOẢNG 700 KG ĐẾN 800 KG

KG3 NẰM TRONG KHOẢNG 8400 KG ĐẾN 8500 KG

GIA1 NẰM TRONG KHOẢNG 10 USD ĐẾN 11 USD

GIA2 NẰM TRONG KHOẢNG 10 USD ĐẾN 11 USD

GIA3 NẰM TRONG KHOẢNG 9 USD ĐẾN 10 USD

TÌM: GIA1, GIA2, GIA3

TÌM: KG1, KG2, KG3

SAU CHO: GIA1 X KG1 + GIA2 X KG2 + GIA3 X KG3 = 190415

TỔNG KG: KG1 + KG2 + KG3 = 18700

KG2 + KG3 = 9200

KG1, KG2, KG3 CHIA HẾT CHO 10

BƯỚC NHẢY STEP GIÁ 0.001

Em có dùng thuật toán Bruteforce nhưng vòng lặp lớn và máy chạy không nổi, anh chị có cách nào hay hơn giúp em ạ!
EM CÓ LƯỢNG TÍNH BẰNG TAY THOẢ MÃN, NẾU CÁC CẶP LƯỢNG VÀ GIÁ ĐẠT KHOẢNG 10 - 15 CẶP THÌ DỪNG CHƯƠNG TRÌNH Ạ!

99,930.50010.519
7,210.00010.3
83,274.500 9.797
Bài đã được tự động gộp:

KG1, KG2, KG3 LẦN LƯỢT

9500
700
8,500
Chạy code . . .
Mã:
Option Explicit

Sub xyz()
  Dim res(1 To 15, 1 To 7)
  Dim sl2&, k&, t#, sl3&, S#, e#, m#, j#, tp#, tt#
  Dim p1#, lP2#, uP2#, lP3#, uP3#, P#, Pm#
 
  S = 190415: e = 0.001
  lP2 = 10:     uP2 = 11
  lP3 = 9:      uP3 = 10
  For sl2 = 700 To 800 Step 10
    p1 = 10
    sl3 = 9200 - sl2
    Do While p1 <= 11
      t = S - 9500 * p1
      P = (t - sl2 * lP2) / sl3
      Pm = (t - sl2 * uP2) / sl3
      If P >= lP3 And Pm <= uP3 Then
        If P >= uP3 Then
          P = (t - uP3 * sl3) / sl2
          j = P / e
          m = Int(j)
          If m <> j Then P = (m + 1) * e
        Else
          P = lP2
        End If
        If Pm <= lP3 Then
          Pm = (t - lP3 * sl3) / sl2
        Else
          Pm = uP2
        End If
        For j = P To Pm Step e
          j = Round(j, 3)
          tp = (t - sl2 * j) / sl3
          tt = tp / e
          If tt = Int(tt) Then
            k = k + 1
            res(k, 1) = 9500: res(k, 2) = p1
            res(k, 3) = sl2: res(k, 4) = j
            res(k, 5) = sl3: res(k, 6) = tp
            res(k, 7) = res(k, 1) * res(k, 2) + res(k, 3) * res(k, 4) + res(k, 5) * res(k, 6)
            If k = 15 Then GoTo Thoat
          End If
        Next j
      End If
      p1 = Round(p1 + e, 3)
    Loop
  Next sl2
Thoat:
  Range("B2").Resize(15, 7) = res
End Sub
 
Lần chỉnh sửa cuối:
Upvote 0
Chạy code . . .
Mã:
Option Explicit

Sub xyz()
  Dim res(1 To 15, 1 To 7)
  Dim sl2&, k&, t#, sl3&, S#, e#, m#, j#, tp#, tt#
  Dim p1#, lP2#, uP2#, lP3#, uP3#, P#, Pm#
 
  S = 190415: e = 0.001
  lP2 = 10:     uP2 = 11
  lP3 = 9:      uP3 = 10
  For sl2 = 700 To 800 Step 10
    p1 = 10
    sl3 = 9200 - sl2
    Do While p1 <= 11
      t = S - 9500 * p1
      P = (t - sl2 * lP2) / sl3
      Pm = (t - sl2 * uP2) / sl3
      If P >= lP3 And Pm <= uP3 Then
        If P >= uP3 Then
          P = (t - uP3 * sl3) / sl2
          j = P / e
          m = Int(j)
          If m <> j Then P = (m + 1) * e
        Else
          P = lP2
        End If
        If Pm <= lP3 Then
          Pm = (t - lP3 * sl3) / sl2
        Else
          Pm = uP2
        End If
        For j = P To Pm Step e
          tp = (t - sl2 * j) / sl3
          tt = tp / e
          If tt = Int(tt) Then
            k = k + 1
            res(k, 1) = 9500: res(k, 2) = p1
            res(k, 3) = sl2: res(k, 4) = j
            res(k, 5) = sl3: res(k, 6) = tp
            res(k, 7) = res(k, 1) * res(k, 2) + res(k, 3) * res(k, 4) + res(k, 5) * res(k, 6)
            If k = 15 Then GoTo Thoat
          End If
        Next j
      End If
      p1 = Round(p1 + e, 3)
    Loop
  Next sl2
Thoat:
  Range("B2").Resize(15, 7) = res
End Sub
Quả là Code của chuyên gia có khác. Code chạy nhanh không tưởng.

Khi cho thêm
Mã:
.....
'    If k = 200 Then GoTo Thoat
    key = p1 & "#" & j & "#" & tp
    If Not Dic.Exists(key) Then Dic.Add (key), Empty Else GoTo Thoat
Code cho ra được 755 kết quả thỏa mãn yêu cầu của đề bài biên độ của SL 2 là từ 700 đến 800 và SL3 là từ 8500 đến 8400 . Thời gian chạy code không quá 2 s
 

File đính kèm

  • Screenshot (274).png
    Screenshot (274).png
    134.3 KB · Đọc: 10
Upvote 0
Vẫn với đề bài trên nhưng bỏ đi điều kiện KG1, KG2, KG3 CHIA HẾT CHO 10 tức là trong code của Anh @ HieuCD ta Thay thành For sl2 = 700 To 800 'Step 10 (bỏ đi Step 10) thì cho ra được 1235 kết quả.
Nhưng nếu tăng thêm KG thành KG1,.....KG(n). và tương ứng tăng thêm GIA1,.....GIA(n) với n<10, và vẫn là KG1=cố định : KG2+KG3+...KGn = Tổng KG-K1 và KG1,....KG(n) chia hết cho 10. và chỉ cần lấy 10-15 kết quả.
Thì phải sửa lại code thế nào.
Xin các anh ra tay chỉ giúp để cho tôi và các thành viên khác có thêm tài liệu học tập, nghiên cứu. và rất có thể sẽ có thành viên nào đó ứng dụng vào trong thực tế công việc.
Trân trọng cảm ơn.
 
Upvote 0
Chạy code . . .
Mã:
Option Explicit

Sub xyz()
  Dim res(1 To 15, 1 To 7)
  Dim sl2&, k&, t#, sl3&, S#, e#, m#, j#, tp#, tt#
  Dim p1#, lP2#, uP2#, lP3#, uP3#, P#, Pm#
 
  S = 190415: e = 0.001
  lP2 = 10:     uP2 = 11
  lP3 = 9:      uP3 = 10
  For sl2 = 700 To 800 Step 10
    p1 = 10
    sl3 = 9200 - sl2
    Do While p1 <= 11
      t = S - 9500 * p1
      P = (t - sl2 * lP2) / sl3
      Pm = (t - sl2 * uP2) / sl3
      If P >= lP3 And Pm <= uP3 Then
        If P >= uP3 Then
          P = (t - uP3 * sl3) / sl2
          j = P / e
          m = Int(j)
          If m <> j Then P = (m + 1) * e
        Else
          P = lP2
        End If
        If Pm <= lP3 Then
          Pm = (t - lP3 * sl3) / sl2
        Else
          Pm = uP2
        End If
        For j = P To Pm Step e
          tp = (t - sl2 * j) / sl3
          tt = tp / e
          If tt = Int(tt) Then
            k = k + 1
            res(k, 1) = 9500: res(k, 2) = p1
            res(k, 3) = sl2: res(k, 4) = j
            res(k, 5) = sl3: res(k, 6) = tp
            res(k, 7) = res(k, 1) * res(k, 2) + res(k, 3) * res(k, 4) + res(k, 5) * res(k, 6)
            If k = 15 Then GoTo Thoat
          End If
        Next j
      End If
      p1 = Round(p1 + e, 3)
    Loop
  Next sl2
Thoat:
  Range("B2").Resize(15, 7) = res
End Sub
Bài của bạn nếu bỏ qua điều kiện thoát sẽ cho ra 755 kết quả.
Có lẽ con số này phải lớn hơn gần 40 lần mới chính xác
 
Upvote 0
Bài của bạn nếu bỏ qua điều kiện thoát sẽ cho ra 755 kết quả.
Có lẽ con số này phải lớn hơn gần 40 lần mới chính xác
Máy tính cộng số thập phân có sai số nên biến "J" với bước nhảy "e" càng về sau sẽ có chênh lệch.
Thêm lệnh làm tròn kết quả sẽ tăng lên

For j = P To Pm Step e
j = Round(j, 3)
.......
 
Upvote 0
Máy tính cộng số thập phân có sai số nên biến "J" với bước nhảy "e" càng về sau sẽ có chênh lệch.
Thêm lệnh làm tròn kết quả sẽ tăng lên

For j = P To Pm Step e
j = Round(j, 3)
.......
Cái này thì 50/50
Nếu tinh thần bài toán là tính toán thì Application.Round mới đúng.
Nhưng đề bài này có dính liu tiền và khối lượng cho nên có thể dùng VBA.Round đúng hơn.

Chú:
Application.Round = khoa học và kỹ thuật (technology).
VBA.Round = tài chính và kỹ nghệ (engineering).
 
Upvote 0
Máy tính cộng số thập phân có sai số nên biến "J" với bước nhảy "e" càng về sau sẽ có chênh lệch.
Thêm lệnh làm tròn kết quả sẽ tăng lên

For j = P To Pm Step e
j = Round(j, 3)
.......
Code của bạn không thể trả về toàn bộ kết quả có lẽ không phải do biến j mà là do P, Pm tính chưa đúng thì phải
 
Upvote 0
Code thử theo 1 cách khoai sắn
Mã:
Option Explicit

Sub abc()
Dim KG1, KG2, KG3
Dim maxGia2, minGia2
Dim maxGia3, minGia3
Dim ghGia2
Dim TongTT
Dim Kq()
Dim rws, i, j, k

TongTT = 190415000
maxGia2 = 11000: minGia2 = 10000
maxGia3 = 10000: minGia3 = 9000
ReDim Kq(1 To 100000, 1 To 7)

KG1 = 9500
For i = 10000 To 11000
    For KG2 = 700 To 800 Step 10
        KG3 = 9200 - KG2
        ghGia2 = (TongTT - KG1 * i - KG3 * minGia3) \ KG2 + 1
        If ghGia2 >= minGia2 Then
            ghGia2 = IIf(ghGia2 > maxGia2, maxGia2, ghGia2)
            For j = minGia2 To ghGia2
                k = TongTT - KG1 * i - KG2 * j
                If k / KG3 = k \ KG3 Then
                    If k \ KG3 >= minGia3 And k \ KG3 <= maxGia3 Then
                        rws = rws + 1
                    
                        Kq(rws, 1) = KG1
                        Kq(rws, 2) = i / 1000
                        Kq(rws, 3) = KG2
                        Kq(rws, 4) = j / 1000
                        Kq(rws, 5) = KG3
                        Kq(rws, 6) = k / KG3 / 1000
                        Kq(rws, 7) = Kq(rws, 1) * Kq(rws, 2) + Kq(rws, 3) * Kq(rws, 4) + Kq(rws, 5) * Kq(rws, 6)
                    End If
                End If
            Next j
        End If
    Next KG2
Next i

With Sheet2
    .UsedRange.Clear
    .Range("A3") = rws
    .Range("A6").Resize(rws, UBound(Kq, 2)) = Kq
End With
End Sub
 
Upvote 0
Web KT

Bài viết mới nhất

Back
Top Bottom