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