动态规划.txt

vb环境下用动态规划方法编的0/1背包问题

Private Sub Command1_Click()
Dim i, j, k, n As Integer
Dim maxw, w   As Integer        ' 定义变量maxw为最大装载量
Dim wei(), v() As Integer    '定义每箱的重量和价值
Dim c() As Integer
Dim x() As Integer

n = Val(InputBox("输入箱数"))   '输入箱数和maxw
maxw = Val(InputBox("tatal weight"))


ReDim wei(1 To n)  '重新定义动态数组
ReDim v(1 To n)
ReDim c(0 To n, 0 To maxw)
ReDim x(1 To n)

For j = 1 To n
  wei(j) = Val(InputBox("weight"))    '输入每箱的重量和价值，做标记x（j）
  v(j) = Val(InputBox("value"))
  
'  x(j) = o
  
  Picture1.Print wei(j);
  Picture1.Print v(j);
  Picture1.Print
Next

For i = 1 To n
  c(i, 0) = 0
    For w = 1 To maxw
       If wei(i) <= w Then
           If v(i) + c(i - 1, w - wei(i)) > c((i - 1), w) Then
               c(i, w) = v(i) + c(i - 1, w - wei(i))
           Else
               c(i, w) = c(i - 1, w)
           End If
       Else
         c(i, w) = c(i - 1, w)
       End If
    Next w
' Picture2.Print c(i, w - 1)
Next i

Picture2.Print c(i - 1, w - 1)
Picture2.Print

For m = n To 2 Step -1
  If c(m, maxw) = c(m - 1, maxw) Then
    x(m) = 0
  Else
    x(m) = 1
    maxw = maxw - wei(m)
  End If
  Picture2.Print x(m);
Next m
   
If c(1, maxw) = 0 Then
   x(1) = 0
Else
   x(1) = 1
End If
Picture2.Print x(1)

End Sub