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

aimisiyou

将物品（重量 ，价值）按照重量从小到大（同时价值从大到小）排序，如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

算法复杂度为O（sum(wi)*n*(小于X的数去重后的个数)）~O（sum(wi)*n*n）。不知道是否有误？

aimisiyou

尝试写出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

aimisiyou 发表于 2019-12-15 20:07
算法复杂度为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

感觉似乎可以用图解法，来简化运算。
如图，最顶部的三个点为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，再添加一点重心横坐标是往右移动的，故不存在这样的五点。
故max（20,38,53,53）=53