網路城邦
回本城市首頁 唐老鴨之家
市長:  副市長:
加入本城市推薦本城市加入我的最愛訂閱最新文章
udn城市資訊科技網路分享【唐老鴨之家】城市/討論區/
討論區Excel VBA 字體:
上一個討論主題 回文章列表 下一個討論主題
0/1背包問題
 瀏覽396|回應0推薦0


等級:6
留言加入好友
Rem === 0/1背包問題 ===
Rem === 一共10件物品,A1:A10放物品價值,B1:B10放物品重量,
Rem === C1放背包容量(重量), E1:E10放最佳解答(取或不取)

Dim h(10) As Boolean
Dim a(10), b(10) As Integer
Dim sa, sb, maxv, capacity As Integer

Private Sub CommandButton1_Click()
capacity = Cells(1, 3) 'knapsack capacity
For i = 1 To 10
h(i) = False
a(i) = Cells(i, 1) 'value of the item
b(i) = Cells(i, 2) 'weight of the item
Next i
sa = 0
sb = 0
maxv = 0
Call try(1)
End Sub

Sub try(i)
h(i) = True
sa = sa + a(i)
sb = sb + b(i)
If i < 10 Then
try (i + 1)
Else
If sa >= maxv And sb <= capacity Then
maxv = sa
Call prt
End If
End If
h(i) = False
sa = sa - a(i)
sb = sb - b(i)
If i < 10 Then
try (i + 1)
Else
If sa >= maxv And sb <= capacity Then
maxv = sa
Call prt
End If
End If
End Sub

Sub prt()
For i = 1 To 10
Cells(i, 5) = h(i)
Next i
End Sub

本文於 修改第 1 次
回應 回應給此人 推薦文章 列印 加入我的文摘

引用
引用網址:http://city.udn.com/forum/trackback.jsp?no=58536&aid=5035737