背包问题

paciguard

为什么两个工具的结果不一样：

jsgj2023

paciguard 发表于 2017-6-22 07:57
为什么两个工具的结果不一样：

你得比较一下看看哪个结果更优!

paciguard

jsgj2023 发表于 2017-6-22 08:23
你得比较一下看看哪个结果更优!

是的，但我觉得背包问题首先是一个数学问题，没有计算机就解决不了吗？所以方法比代码重要。。。

香川群子

看懂了，写了个递归过程，可以把所有组合都提取出来。

香川群子

'下面代码随机选取1种组合
    i = m: j = h
    Randomize
    Do
        t = j
        Do
            If DP(i, j) = DP(i, j - 1) Then j = j - 1 Else Exit Do
        Loop Until j = 0
        j = j + Int(Rnd * (t - j + 1))

        t = i
        Do
            If DP(i, j) = DP(i - 1, j) Then i = i - 1 Else Exit Do
        Loop Until i = 1
        i = i + Int(Rnd * (t - i + 1))

        jg(1, 0) = jg(1, 0) + 1: jg(1, i) = 1: j = j - sj(i, 1)
        i = i - 1
    Loop Until DP(i, j) = 0

laoau128

paciguard 发表于 2017-6-22 08:32
是的，但我觉得背包问题首先是一个数学问题，没有计算机就解决不了吗？所以方法比代码重要。。。

这个是什么

三坛老窖

香川群子 发表于 2017-6-23 22:12
看懂了，写了个递归过程，可以把所有组合都提取出来。

你附件中的dg_1过程是什么意思？是为了统计解的数量吗？
当数据量稍大（例如物品数量=100）时，进入该过程就出不来了（递归组合爆炸了）。

这几天我也一直在琢磨如何有效的从DP表中提取出所有的可行解，这是个挺绕人的问题。
我附件中的代码能从DP表中提取多组解，但是否能全部提取，现在还搞不清楚。------------------------------------------
DP_01背包v1.rar (726.72 KB, 下载次数: 37)

2017-6-24 23:06 上传

点击文件名下载附件

aman1516

标记一下，好好向大师们学习

香川群子

提取解的能力有所提高，但似乎仍有遗漏。

香川群子

发现问题了。只要改一下顺序，就完美了。

1. Sub dg2(i&, j&, t&) '提取全部满足背包尺寸的最大价值的k个组合解
   
2.     Dim i2&, s$, v&, w&
   
3.     If DP(i, j) = 0 Then
   
4.         jg(0, k) = t
   
5.         s = String(m, "0"): w = 0: v = 0
   
6.         For i2 = i + 1 To m
   
7.             If jg(i2, k) Then jg(i2, k + 1) = 1: Mid(s, i2, 1) = 1: w = w + sj(i2, 1): v = v + sj(i2, 2)
   
8.         Next
   
9.         'k = k + 1: dic(s) = k '返回所有可能解
   
10.         If w <= h Then If v = DP(m, h) Then k = k + 1: dic(s) = k '舍去部分价值接近最大值的解
    
11.         Exit Sub
    
12.     End If
    
13.    
    
14.     If DP(i, j) = DP(i - 1, j) Then Call dg2(i - 1, j, t) '当前物品不可放入时(放入会超过背包尺寸)
    
15.     If j >= sj(i, 1) Then '确保是可放入背包尺寸的物品
    
16.         If DP(i, j) >= sj(i, 2) Then '价值可扣除时
    
17.             If DP(i, j) - sj(i, 2) = DP(i - 1, j - sj(i, 1)) Then '当前价值扣除价值=未放入背包时的价值
    
18.                 jg(i, k) = 1: Call dg2(i - 1, j - sj(i, 1), t + 1): jg(i, k) = 0 '本物品记录在组合内
    
19.             Else
    
20.                 If DP(i, j) - sj(i, 2) = DP(i, j - sj(i, 1)) Then Call dg2(i, j - 1, t) '不含当前物品时
    
21.             End If
    
22.         End If
    
23.     End If
    
24. End Sub

复制代码

把当前物品不可放入这一句放到最前面，就对了。

现在的递归过程，和生成DP表过程的做法正好是相反的，所以就对了。