采用动态规划求解0-1背包问题最优解

aimisiyou · 发表于 2019-12-15 18:48:09

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

×

本帖最后由 aimisiyou 于 2019-12-15 19:45 编辑

将物品（重量，价值）按照重量从小到大（同时价值从大到小）排序，如lst='（（3  15）（3  11）（3 9）（4 12）（13 26）（15 90）（16  12））。现定义f(x,lst)为重量不超过x，能从lst取出的最大价值和。可得动态递归方程式
f(x,lst)=0  当x<min(wi)时；
f(x+1,lst） = max{f(x,lst) ,max{f(x+1-wi ,  lst-(wi,ci)) +ci }};其中wi<=x+1
即有f(1,'（（3  15）（3  11）（3 9）（4 12）（13 26）（15 90）（16  12））)=0
f(2,'（（3  15）（3  11）（3 9）（4 12）（13 26）（15 90）（16  12））)=0
f(3,'（（3  15）（3  11）（3 9）（4 12）（13 26）（15 90）（16  12））)=max{f(2,lst), max{f(3-3,lst-(3 15))+15, f(3-3,lst-(3 11))+11,f(3-3,lst-(3 9))+9}}=15
f(4,'（（3  15）（3  11）（3 9）（4 12）（13 26）（15 90）（16  12））)=max{f(3,lst), max{f(4-3,lst-(3 15))+15, f(4-3,lst-(3 11))+11,f(4-3,lst-(3 9))+9}}=15
f(5,'（（3  15）（3  11）（3 9）（4 12）（13 26）（15 90）（16  12））)=max{f(4,lst), max{f(5-3,lst-(3 15))+15, f(5-3,lst-(3 11))+11,f(5-3,lst-(3 9))+9,f(5-4,lst-(4  12))+12}}=15
f(6,'（（3  15）（3  11）（3 9）（4 12）（13 26）（15 90）（16  12））)=max{f(5,lst), max{f(6-3,lst-(3 15))+15, f(6-3,lst-(3 11))+11,f(6-3,lst-(3 9))+9,f(6-4,lst-(4  12))+12}}=max{f(5,lst), max{f(6-3,lst-(3 15))+15, f(6-3,lst-(3 11))+11,f(6-3,lst-(3 9))+9,f(6-4,lst-(4  12))+12}}=26

aimisiyou · 发表于 2019-12-15 20:00:54

本帖最后由 aimisiyou 于 2019-12-15 20:02 编辑

算法复杂度为O（sum(wi)*n*(小于X的数去重后的个数)）~O（sum(wi)*n*n）

aimisiyou · 发表于 2019-12-15 23:17:11

尝试写出f(17,lst1)=max{f(16,lst1),max{f(3,lst1)+f(17-3,lst2),f(4,lst1)+f(17-4,lst5),f(13,lst1)+f(17-13,lst7),f(15,lst1)+f(17-15,lst7),f(16,lst1)+f(17-16,lst7)}}
=max{f(16,lst1),max{f(3,lst1)+f(14,lst2),f(4,lst1)+f(13,lst5),f(13,lst1)+f(4,lst7),f(15,lst1)+f(2,lst7),f(16,lst1)+f(1,lst7)}}
=max{f(16,lst1),max{f(3,lst1)+f(14,lst2),f(4,lst1)+f(13,lst5),f(13,lst1)+0,f(15,lst1)+0,f(16,lst1)+0}}
=max{f(16,lst1),max{f(3,lst1)+f(14,lst2),f(4,lst1)+f(13,lst5),f(16,lst1)+0}}
=max{90,max{15+32,15+26,90}}
=90

aimisiyou · 发表于 2019-12-15 23:50:45

本帖最后由 aimisiyou 于 2019-12-15 23:53 编辑

可见，当x-w_i<w_(i+1),不用去一一算max{f(w_i,lst1)+f(x-w_i),lsti),f(w_(i+1),lst1)+f(x-w_i+1),lstk),……}可简化运算=max{f(w_i,lst1)+0,f(w_(i+1),lst1)+0,……f(w_(i+k),lst1)+0},由于f(x,lst1)是非减函数，故=f(w_(i+k),lst1)。

aimisiyou · 发表于 2019-12-16 01:38:00

f(20,lst1)=max(f(19,lst1),max{f(3,lst1)+f(17,lst2),f(4,lst1)+f(16,lst3),f(5,lst1)+f(15,lst4),f(6,lst1)+f(14,lst5),f(8,lst1)+f(12,lst6),f(10,lst1)+f(10,lst7)})
=max(53,max{8+45,20+31,20+31,20+18,28+12,38+18})
=56

kmliro_2017 · 发表于 2019-12-16 07:17:59

谢谢分享！！！！

aimisiyou · 发表于 2019-12-16 07:42:25

本帖最后由 aimisiyou 于 2019-12-16 10:39 编辑

aimisiyou 发表于 2019-12-15 20:00
算法复杂度为O（sum(wi)*n*(小于X的数去重后的个数)）~O（sum(wi)*n*n）

算法复杂度是不对的，应该是O(sum(wi)*2^n)。类似卷积，f(x,lst)=max(f(x-1,lst),max{f(w1,lst)+f(x-w1,lst-lst1),f(w2,lst)+f(x-w2,lst-lst2),f(w3,lst)+f(x-w3,lst-lst3),……，f(wn,lst)+f(x-wn,lst-lstn)})

aimisiyou · 发表于 2019-12-16 11:15:10

令lst=((x1,y1)(x2,y2)(x3,y3)……（x_n,y_n）),其中xi没有重复的项，xi是递增的。
sum(x1,x2……x_i)<=x<sum(x1,x2……x_i,x_(i+1))且x_k<=x，则先考虑y_i递增和递减两种情况。

aimisiyou · 发表于 2019-12-16 14:27:31

本帖最后由 aimisiyou 于 2019-12-16 18:06 编辑

感觉似乎可以用图解法，来简化运算。
如图，最顶部的三个点为A（4,20），D（6,15），E（8,18），其重心为（（XA+XD+XE）/3,（YA+YD+YE）/3）=(18/3,53/3).
故当背包容量为18时，装入三个物品的最大价值为53.
最顶部的四个点为A（4,20），D（6,15），E（8,18），F（10,12），其重心为（（XA+XD+XE+XF）/4,（YA+YD+YE+YF）/4）=(28/4,65/4).
故当背包容量为28时，装入四个物品的最大价值为65.

当背包容量为X时，如何取最大价值和？
也就是选取K个点，其重心的横坐标<=x/k,重心的纵坐标尽可能的大，分别考虑K=1,2,3,4……,x/min(xi)时的情况，取k*重心纵坐标y所得的值最大。

例如求f（18）
当K=1时，考虑坐标点横坐标小于x/1=18/1=18内的所有点，最高点为（4,20），故K*y=1*20=20
当K=2时，考虑中点坐标横坐标小于x/2=18/2=9内的所有点，最高两点为（4,20）和（8,18），其中点为（6,19），故K*y=2*19=38
当K=3时，考虑重心坐标横坐标小于x/3=18/3=6内的所有点，最高三点重心坐标为（6,53/3）,故故K*y=3*（53/3）=53
当K=4时，考虑重心坐标横坐标小于x/4=18/4=4.5内的所有点，最左边四点重心坐标为（4.5,53/4）,故故K*y=4*（53/4）=53
当K=5时，考虑重心坐标横坐标小于x/5=18/5=3.6内的所有点，而最左边四点重心横坐标为4.5，再添加一点重心横坐标是往右移动的，故不存在这样的五点,更不用提K=x/min(xi)=18/3=6时的情况（不存在）。
故f(18)=max（20,38,53,53）=53

aimisiyou · 发表于 2019-12-16 20:22:58

(setq x 385 pts '((24 70)(14 38)(45 93)(40 80)(35 70)(19 36)(27 38)(72 99)(66 89)(62 77)(25 30)(83 94)(42 43)(55 49)(71 62)(59 48)(45 29)))
(setq pts (vl-sort pts '(lambda (ea eb) (< (car ea) (car eb)))))
(apply 'command (cons "pline" (reverse (cons "c" (reverse pts)))))
(mapcar '(lambda (x) (command "circle" x 2 "")) pts)

aimisiyou · 发表于 2019-12-16 20:54:04

本帖最后由 aimisiyou 于 2019-12-16 21:52 编辑

先将pts按x值升序排列，可得前11个点的横坐标值之和371小于385，此时y值之和为576。即最多可选取11个点。385/11=35
_$ (setq pts (vl-sort pts '(lambda (ea eb) (< (car ea) (car eb)))))
((14 38) (19 36) (24 70) (25 30) (27 38) (35 70) (40 80) (42 43) (45 93) (45 29) (55 49) (59 48) (62 77) (66 89) (71 62) (72 99) (83 94))
_$

然后将pts按y值降序排列，选取前k个点，直至满足前k个点的横坐标之和<=385,得k=6,此时y值之和为532，6点中y值最低为77.
_$ (setq pts (vl-sort pts '(lambda (ea eb) (> (cadr ea) (cadr eb)))))
((72 99) (83 94) (45 93) (66 89) (40 80) (62 77) (24 70) (35 70) (71 62) (55 49) (59 48) (42 43) (14 38) (27 38) (19 36) (25 30) (45 29))
然后将pts按到点（35,77）的距离值升序排列，再选取前p个点，直至满足前p个点的横坐标之和<=385,得p=8,此时y值之和为571，8点中y值最低为43
_$ (setq pts (vl-sort pts '(lambda (ea eb) (< (distance ea '(35 77))(distance eb '(35 77))))))
((40 80) (35 70) (24 70) (45 93) (62 77) (66 89) (55 49) (42 43) (59 48) (71 62) (27 38) (72 99) (19 36) (14 38) (25 30) (45 29) (83 94))
_$

aimisiyou · 发表于 2019-12-16 23:50:44

本帖最后由 aimisiyou 于 2019-12-16 23:52 编辑

算法如下1、将pts按横坐标升序排列，取前K个点的横坐标之和sum（x1,……x_k）刚好小于X（再加一个就大于）;
2、前K个点中取出两点(尽量先从x值大y值低的点选取)，使其满足xi+xj+x-sum（x_k）>x_k，
2.1若不满足，程序结束，最大值为sum(y1,……y_k)
2.2两点相加，得到（xi+xj+x-sum（x_k）,yi+yj），然后从K点之后的点中选取x_t,x_t横坐标不大于xi+xj+x-sum（x_k），纵坐标取大于yi+yj的最大值;
3、转至2，从前（K-1）个点中选取两点……

aimisiyou · 发表于 2019-12-17 00:18:21

本帖最后由 aimisiyou 于 2019-12-17 01:46 编辑

_$ (setq w_tol 1000 wlst '(80 82 85 70 72 70 66 50 55 25 50 55 40 48 50 32 22 60 30 32 40 38 35 32 25 28 30 22 50 30 45 30 60 50 20 65 20 25 30 10 20 25 15 10 10 10 4 4 2 1)  clst '(220 208 198 192 180 180 165 162 160 158 155 130 125 122 120 118 115 110 105 101 100 100 98 96 95 90 88 82 80 77 75 73 72 70 69 66 65 63 58 56 50 30 20 15 10 8 5 3 1))
(setq pts (mapcar '(lambda (x y) (list x y)) wlst  clst))
(setq pts (vl-sort pts '(lambda (ea eb) (< (car ea) (car eb)))))
(mapcar '(lambda (x) (command "circle" x 0.1)) pts)
(220 208 198 192 180 180 165 162 160 158 155 130 125 122 120 118 115 110 105 101 100 100 98 96 95 90 88 82 80 77 75 73 72 70 69 66 65 63 58 56 50 30 20 15 10 8 5 3 1)
((80 220) (82 208) (85 198) (70 192) (72 180) (70 180) (66 165) (50 162) (55 160) (25 158) (50 155) (55 130) (40 125) (48 122) (50 120) (32 118) (22 115) (60 110) (30 105) (32 101) (40 100) (38 100) (35 98) (32 96) (25 95) (28 90) (30 88) (22 82) (50 80) (30 77) (45 75) (30 73) (60 72) (50 70) (20 69) (65 66) (20 65) (25 63) (30 58) (10 56) (20 50) (25 30) (15 20) (10 15) (10 10) (10 8) (4 5) (4 3) (2 1))
((2 1) (4 5) (4 3) (10 56) (10 15) (10 10) (10 8) (15 20) (20 69) (20 65) (20 50) (22 115) (22 82) (25 158) (25 95) (25 63) (25 30) (28 90) (30 105) (30 88) (30 77) (30 73) (30 58) (32 118) (32 101) (32 96) (35 98) (38 100) (40 125) (40 100) (45 75) (48 122) (50 162) (50 155) (50 120) (50 80) (50 70) (55 160) (55 130) (60 110) (60 72) (65 66) (66 165) (70 192) (70 180) (72 180) (80 220) (82 208) (85 198))
(nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil)
_$  (apply '+ (mapcar 'car  (member (nth 36 pts) (reverse pts))))
1039
_$ (apply '+ (mapcar 'car  (member (nth 35 pts) (reverse pts))))
989
_$  (apply '+ (mapcar 'cadr  (member (nth 35 pts) (reverse pts))))
2788

1000-989=11

_$ (setq pts1 (reverse (member (nth 35 pts) (reverse pts))))
(setq pts2 (cdr (member (nth 35 pts) pts)))
((2 1) (4 5) (4 3) (10 56) (10 15) (10 10) (10 8) (15 20) (20 69) (20 65) (20 50) (22 115) (22 82) (25 158) (25 95) (25 63) (25 30) (28 90) (30 105) (30 88) (30 77) (30 73) (30 58) (32 118) (32 101) (32 96) (35 98) (38 100) (40 125) (40 100) (45 75) (48 122) (50 162) (50 155) (50 120) (50 80))
((50 70) (55 160) (55 130) (60 110) (60 72) (65 66) (66 165) (70 192) (70 180) (72 180) (80 220) (82 208) (85 198))
_$ (setq pts1 (vl-sort pts1 '(lambda (ea eb) (< (cadr ea) (cadr eb)))))
((2 1) (4 3) (4 5) (10 8) (10 10) (10 15) (15 20) (25 30) (20 50) (10 56) (30 58) (25 63) (20 65) (20 69) (30 73) (45 75) (30 77) (50 80) (22 82) (30 88) (28 90) (25 95) (32 96) (35 98) (38 100) (40 100) (32 101) (30 105) (22 115) (32 118) (50 120) (48 122) (40 125) (50 155) (25 158) (50 162))
_$ (setq pts2 (vl-sort pts2 '(lambda (ea eb) (> (cadr ea) (cadr eb)))))
((80 220) (82 208) (85 198) (70 192) (70 180) (72 180) (66 165) (55 160) (55 130) (60 110) (60 72) (50 70) (65 66))
_$

80-11=69,
即从pts1中选取几个点，它们x方向和值大于69，且y轴方向和值最小。
即用 (10 8) (10 10) (10 15) (15 20) (25 30)五个点换（80,220）

pts1=((2 1) (4 3) (4 5) (20 50) (10 56) (30 58) (25 63) (20 65) (20 69) (30 73) (45 75) (30 77) (50 80) (22 82) (30 88) (28 90) (25 95) (32 96) (35 98) (38 100) (40 100) (32 101) (30 105) (22 115) (32 118) (50 120) (48 122) (40 125) (50 155) (25 158) (50 162)(80 220))
pt2=( (82 208) (85 198) (70 192) (70 180) (72 180) (66 165) (55 160) (55 130) (60 110) (60 72) (50 70) (65 66))

11-(80-70)=1
82-1=81
即从pts1中选取几个点，它们x方向和值大于81，且y轴方向和值最小。
即用 ((2 1) (4 3) (20 50)  (30 58) (25 63)  五个点换（82,208）

pts1=( (4 5)  (10 56) (20 69) (20 65)(30 73) (45 75) (30 77) (50 80) (22 82) (30 88) (28 90) (25 95) (32 96) (35 98) (38 100) (40 100) (32 101) (30 105) (22 115) (32 118) (50 120) (48 122) (40 125) (50 155) (25 158) (50 162)(80 220) (82 208))
pt2=( (85 198) (70 192) (70 180) (72 180) (66 165) (55 160) (55 130) (60 110) (60 72) (50 70) (65 66))
_$ (apply '+ (mapcar 'car  pts1))
1000
_$

_$ (apply '+ (mapcar 'cadr  pts1))
2958

即从pts1中选取几个点，它们x方向和值大于85，且y轴方向和值最小且小于198。不存在。
即从pts1中选取几个点，它们x方向和值大于70，且y轴方向和值最小且小于192。
即用 ((30 73） (40 75)  两个点换（70  192）
pts1=( (4 5)  (10 56) (20 69) (20 65)(30 77) (50 80) (22 82) (30 88) (28 90) (25 95) (32 96) (35 98) (38 100) (40 100) (32 101) (30 105) (22 115) (32 118) (50 120) (48 122) (40 125) (50 155) (25 158) (50 162)（70  192）(80 220) (82 208))
pt2=( (70 180) (72 180) (66 165) (55 160) (55 130) (60 110) (60 72) (50 70) (65 66))

_$ (setq pts '( (4 5)  (10 56) (20 69) (20 65)(30 77) (50 80) (22 82) (30 88) (28 90) (25 95) (32 96) (35 98) (38 100) (40 100) (32 101) (30 105) (22 115) (32 118) (50 120) (48 122) (40 125) (50 155) (25 158) (50 162)(70  192)(80 220) (82 208)))
(apply '+ (mapcar 'car  pts))
((4 5) (10 56) (20 69) (20 65) (30 77) (50 80) (22 82) (30 88) (28 90) (25 95) (32 96) (35 98) (38 100) (40 100) (32 101) (30 105) (22 115) (32 118) (50 120) (48 122) (40 125) (50 155) (25 158) (50 162) (70 192) (80 220) (82 208))
995
_$ (apply '+ (mapcar 'cadr  pts))
3002
_$

70-5=65
即用 ((20 65） (50 80)  两个点换（70  180）
pts1=( (4 5)  (10 56) (20 69) (30 77)  (22 82) (30 88) (28 90) (25 95) (32 96) (35 98) (38 100) (40 100) (32 101) (30 105) (22 115) (32 118) (50 120) (48 122) (40 125) (50 155) (25 158) (50 162)（70  180）(70  192)(80 220) (82 208))
pt2=( (66 165) (55 160) (55 130) (60 110) (60 72) (50 70) (65 66))

(apply '+ (mapcar 'car  pts1))
((4 5) (10 56) (20 69) (30 77) (22 82) (30 88) (28 90) (25 95) (32 96) (35 98) (38 100) (40 100) (32 101) (30 105) (22 115) (32 118) (50 120) (48 122) (40 125) (50 155) (25 158) (50 162) (70 180) (70 192) (80 220) (82 208))
995
_$ (apply '+ (mapcar 'cadr  pts1))
3037
_$

aimisiyou · 发表于 2019-12-17 02:22:46

似乎找到了退换的理想方法。

aimisiyou · 发表于 2019-12-17 14:10:28

本帖最后由 aimisiyou 于 2019-12-17 14:14 编辑

选取的点组合值须落在蓝线框内才基本满足要求（即y向增加量大于x向增加量和y向减少量大于x向减少量，这是最基本要求）。

账号		自动登录	找回密码
密码			立即注册

[原创] 采用动态规划求解0-1背包问题最优解

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。