谁能帮我解释一下 这段01背包问题的VB代码

2025-06-23 02:02:25
推荐回答(1个)
回答1:

Dim p, y As Integer '这里定义了两个窗体模块级变量,p是背包的总质量,y是物品总数

Private Sub Form_click() '窗体单击事件
'通过输入框提示输入物品数、总质量
y = InputBox("请输入可装的物品数 , 1 p = InputBox("请输入背包的总质量")

'声明一个二维数据,用来保存物品的质量和价值
Dim a(1 To 2, 1 To 100) As Integer
For J = 1 To y '循环提示用户依次输入每个物品的质量和价值,输入结果保存到数组a中,J变量是当前物品序号
For i = 1 To 2 'i变量用来判断要输入质量还是价值
If (i = 1) Then 'i是1时提示输入当前物品的质量
a(i, J) = InputBox("请输入第" & J & "件物品的质量")
End If
If (i = 2) Then 'i是1时提示输入当前物品的价值
a(i, J) = InputBox("请输入第" & J & "件物品的价值")
End If
Next
Next

'给J变量赋初值为2,即从第2个物品开始循环处理
J = 2
Do
For i = J To y '将J的前一物品依次跟J到y的物品质量进行比较,如果J的前一物品的质量大则当前物品i互换位置,通过这个循环后J的前一物品的质量是J-1到y中最小的一个。
'在这个for的循环中J是不变的,i依次递增,直到y
If a(1, J - 1) > a(1, i) Then '前一物品的质量大时互换位置
t = a(1, J - 1)
a(1, J - 1) = a(1, i)
a(1, i) = t
t = a(2, J - 1)
a(2, J - 1) = a(2, i)
a(2, i) = t
End If
Next i

J = J + 1
Loop Until J > y

Dim max As Integer
Dim m As Integer
Dim n As Integer
Dim k As Integer
max = 0
m = 0
n = 0
k = 1
Call try(p, max, m, n, k, a())
MsgBox "可装载的最大价值为" & max & "!!"

End Sub
Private Sub try(ByVal p As Integer, ByRef max As Integer, ByVal m As Integer, ByVal n As Integer, ByVal k As Integer, ByRef a() As Integer)
'*参数p:背包总质量
'*参数max:可装载的最大价值,注意这里前面用了ByRef关键字,表示传送的是地址,即在这个过程中的max变量就是Form_Click()事件中声明的max变量,对max的修改会影响Form_Click()事件中的max
'*参数m:累计质量
'*参数n:累计价值
'*参数k:当前物品序号
'*参数a():保存质量、价值的二维数组,这里传送的也是地址
'*
If k < y Then
'递归调用
Call try(p, max, m, n, k + 1, a())
End If

For i = k To y
If m + a(1, i) <= p Then '累计质量未超过总质量时继续处理
If k < y - 1 Then
'递归调用
Call try(p, max, m, n, k + 1, a())
End If
m = m + a(1, i) '质量累加
n = n + a(2, i) '价值累加
k = i
If n > max Then
max = n
End If
Else
Exit For
End If
Next i
End Sub