明天就要去遠足了，小綠正打包她的行李，她家有下列五種零食：
名稱
|
大小
|
滿足感
|
海苔
|
3
|
4
|
花生米
|
4
|
5
|
點心麵
|
7
|
10
|
洋芋片
|
8
|
11
|
巧克力
|
9
|
13
|
而這五種零食一定要一整包放進背包不可以打散，現在有一個大小為 N (N<=100)的背包要用來裝零食，請問她可以獲得的最大滿足感為多少？
輸入1：17
輸出1：24
輸入2：100
輸出2：144
(網路參考：http://www.tcgs.tc.edu.tw/~sagit/cpp/q12.htm)
(網路參考：http://www.tcgs.tc.edu.tw/~sagit/cpp/q12.htm)
Private Sub Form_Load()
回覆刪除Me.Hide
Dim x(5), y(5), ans(100) As Integer
Dim a As Boolean
Open App.Path & "\in.txt" For Input As #1
Open App.Path & "\out.txt" For Output As #2
Do While Not EOF(1)
Input #1, n
x(1) = 3: x(2) = 4: x(3) = 7: x(4) = 8: x(5) = 9
y(1) = 4: y(2) = 5: y(3) = 10: y(4) = 11: y(5) = 13
For i = 1 To 5
For j = 1 To n
If j >= x(i) Then
If (ans(j - x(i)) + y(i)) > ans(j) Then ans(j) = ans(j - x(i)) + y(i)
End If
Next
Next
Print #2, ans(n)
Loop
Close
Close
End
End Sub
Private Sub Form_Load()
回覆刪除Me.Hide
Open App.Path & "\in.txt" For Input As #1
Open App.Path & "\out.txt" For Output As #2
Input #1, n
a = Array(0, 3, 4, 7, 8, 9)
b = Array(0, 4, 5, 10, 11, 13)
Sum = 0
For i = 5 To 1 Step -1
Do While n >= a(i)
n = n - a(i)
Sum = Sum + b(i)
Loop
Next i
Print #2, Sum
Close #2
Close #1
End
End Sub
程式只能處理一個輸入，我本來也是這樣解題，但是因為輸出後只有第一組輸出跟範例輸出相同，第二組就差1了，所以是去網路參考才解出來的。
回覆刪除當輸入99是143，再輸入100因為沒有重量=1的資料所以應該也是143?
回覆刪除在問看看老師吧，我跟你是同樣想法，只是答案不對，才去參考網路參考。
回覆刪除100 = (10*9)+7+3 (重量總和)
回覆刪除144 = (10*13)+10+4
所以答案是沒有錯的
了解，更改好了~
回覆刪除Private Sub Form_Load()
Me.Hide
Open App.Path & "\in.txt" For Input As #1
Open App.Path & "\out.txt" For Output As #2
Dim t As Boolean
Input #1, n
a = Array(0, 3, 4, 7, 8, 9)
b = Array(0, 4, 5, 10, 11, 13)
Sum = 0
For i = 5 To 1 Step -1
Do While n >= a(i)
n = n - a(i)
If n < a(i) And n <> 0 Then
For j = 5 To 1 Step -1
t = False
If n = a(j) Then t = True: Exit For
Next j
If t = False Then n = n + a(i): Exit Do
End If
Sum = Sum + b(i)
Loop
Next i
If Sum = 0 Then
For k = 1 To 5
If n > a(k) Then Sum = b(k)
Next k
End If
Print #2, Sum
Close #2
Close #1
End
End Sub
結合你我程式由1至100結果比較，一樣為T，不同為F
回覆刪除Private Sub Form_Load()
Me.Hide
Open App.Path & "\in.txt" For Input As #1
Open App.Path & "\out.txt" For Output As #2
Dim t As Boolean
Dim x(5), y(5), ans(10000) As Integer
Dim a As Boolean
c = Array(0, 3, 4, 7, 8, 9)
b = Array(0, 4, 5, 10, 11, 13)
x(1) = 3: x(2) = 4: x(3) = 7: x(4) = 8: x(5) = 9
y(1) = 4: y(2) = 5: y(3) = 10: y(4) = 11: y(5) = 13
n = 0
Do While n < 100
n = n + 1
nn = n
For i = 1 To 5
For j = 1 To n
If j >= x(i) Then
If (ans(j - x(i)) + y(i)) > ans(j) Then ans(j) = ans(j - x(i)) + y(i)
End If
Next
Next
Sum = 0
For i = 5 To 1 Step -1
Do While nn >= c(i)
nn = nn - c(i)
If nn < c(i) And nn <> 0 Then
For j = 5 To 1 Step -1
t = False
If nn = c(j) Then t = True: Exit For
Next j
If t = False Then nn = nn + c(i): Exit Do
End If
Sum = Sum + b(i)
Loop
Next i
If Sum = 0 Then
For k = 1 To 5
If nn > c(k) Then Sum = b(k)
Next k
End If
If ans(n) = Sum Then Print #2, "T" Else Print #2, "F"
Loop
Close #2
Close #1
End
End Sub
結果全部為T :P
小冰、哲好，
回覆刪除你們做的很好。這樣的極限組合問題，用手算是不容易的。(我的數學功力也不是很強，哈)，但是，用程式來做，可以用這樣類似「暴力」的方式來解。
反正我一個一個代進去，比較好的答案就留著，一定是「堆」的出極限的。
只有一個小地方可以改進的，(雞蛋裡挑骨頭也是很重要的)，
可以先將這ans(100)全做出來，之後，再讀取要那幾個n，直接輸出ans(n)。
這個暑假你們兩個表現很好，開學後的第一個星期一，我們再來認真討論一下，並定一下規則，考一考之後，先暫定下正選手是誰哦，加油。