动态规划_01背包问题.frm

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

VERSION 5.00
Begin VB.Form Form1 
   Caption         =   "Form1"
   ClientHeight    =   3135
   ClientLeft      =   60
   ClientTop       =   465
   ClientWidth     =   4845
   LinkTopic       =   "Form1"
   ScaleHeight     =   3135
   ScaleWidth      =   4845
   StartUpPosition =   3  '窗口缺省
   Begin VB.TextBox Text1 
      Height          =   2175
      Left            =   240
      MultiLine       =   -1  'True
      TabIndex        =   2
      Top             =   120
      Width           =   4335
   End
   Begin VB.CommandButton Command2 
      Caption         =   "退出"
      Height          =   495
      Left            =   2760
      TabIndex        =   1
      Top             =   2520
      Width           =   1815
   End
   Begin VB.CommandButton Command1 
      Caption         =   "计算"
      Height          =   495
      Left            =   240
      TabIndex        =   0
      Top             =   2520
      Width           =   1815
   End
End
Attribute VB_Name = "Form1"
Attribute VB_GlobalNameSpace = False
Attribute VB_Creatable = False
Attribute VB_PredeclaredId = True
Attribute VB_Exposed = False
Private Sub Command1_Click()
Dim i, j, k, Num As Integer
Dim MaxWeight, WR As Integer '定义变量MaxWeight为最大装载量,W为剩余容量
Dim W(), P() As Integer '定义每箱的重量和价值
Dim f() As Integer '最优值函数
Dim X() As Integer '表示那些物品被放入。放入的是1，否则为零

Num = Val(InputBox("请输入物品数量：")) '输入箱数和MaxWeight
Text1 = "物品个数为" & Num & "；" & vbCrLf
MaxWeight = Val(InputBox("背包容量为："))
Text1 = Text1 & "背包的容量为" & MaxWeight & "；" & vbCrLf
ReDim W(1 To Num) '重新定义动态数组大小
ReDim P(1 To Num)
ReDim f(0 To Num, 0 To MaxWeight)
ReDim X(1 To Num)

'输入每个物品的重量和价值
For j = 1 To Num
  W(j) = Val(InputBox("第" & j & "个物品的重量为："))
  P(j) = Val(InputBox("第" & j & "个物品的价值为："))
  Text1 = Text1 & "第" & j & "个物品的重量为" & W(j) & "，价值为" & P(j) & "；" & vbCrLf
Next j

'建立动态规划树
For i = 1 To Num
    f(i, 0) = 0  '清零
    For WR = 1 To MaxWeight
       If W(i) <= WR Then
           If P(i) + f(i - 1, WR - W(i)) > f((i - 1), WR) Then  '动态规划公式
               f(i, WR) = P(i) + f(i - 1, WR - W(i))
           Else
               f(i, WR) = f(i - 1, WR)
           End If
       Else
         f(i, WR) = f(i - 1, WR)
       End If
    Next WR
Next i
Text1 = Text1 & "最大价值为" & f(Num, MaxWeight) & "；" & vbCrLf

'从后往上找最优解
For m = Num To 2 Step -1
  If f(m, MaxWeight) = f(m - 1, MaxWeight) Then
    X(m) = 0
  Else
    X(m) = 1
    MaxWeight = MaxWeight - W(m)
  End If
Next m
   
'对X(1)单独讨论
If f(1, MaxWeight) = 0 Then
   X(1) = 0
Else
   X(1) = 1
End If

'输出物品序号
For i = 1 To Num
    temp = temp + X(i)
Next i
If temp = 0 Then
    Text1 = Text1 & "没有物品可以放入背包。"
Else
    For i = 1 To Num
        If X(i) <> 0 Then Text1 = Text1 & i & " "
    Next i
    Text1 = Text1 & "个物品被放入背包。"
End If
End Sub

'退出程序
Private Sub Command2_Click()
End
End Sub