经典算法问题——“0” “1”背包问题
对于“”0 “ 1”背包问题相信大家对于网上的问题一定找了很多,无非两种算法,即——
(1)方向为从上到下的进行输出的问题
(2)方向为从下到上的一次输出的问题
V为所放入的物品的价值所在 W为所放入的物品的容量
C设为背包的总容量
v1=1 | v2=3 | v3=5 | v4=9 |
w1=2 |
w2=3 | w3=4 | w4=7 |
如何根据给出的填充好下面的表格:
i/j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
1 | |||||||||||
2 | |||||||||||
3 | |||||||||||
4 |
其中I对应的列为物品数目(我列举的例子中只放入了三个物品,所以对应的行有四行)
其中j对应的行为物品数目(我列举的例子中只放入了三个物品,所以对应的行有10列 )
PS:其中“0列” 只是为了补位用的 ,可根据需要进行相应的应用或者不用
具体的规则如下: m(i,j)= m(i+1,j) j<w(i) //不放入物品时候执行的方法
= Max【m(i+1,j);m(i+1,j-w(i))+v(i)】 j>w(i) //放入物品时候的执行的方法
i/j |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
1 | |||||||||||
2 | |||||||||||
3 | |||||||||||
4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 9 | 9 | 9 | 9 |
对于执行方法 m(i,j)=m(i+1,j)时 此时需要注意的是,执行的顺序的从最下面进行相应的执行,一行一行的进行填充,第四个为最小的单元,为第一个放入包中的物品。
对于网上还有资料进行展示的是m(i,j)=m(i-1,j)时候此时需要注意的是,执行的顺序的从最上面进行相应的执行,即第一个物品为最小的单元,为第一个放入包中的物品。
同时!!!!!!需要注意的是 :每一行事实上只有放一个物品 一定要摆脱每一行可以放很多物品的错误想法
具体执行的方法: 1.考虑 j 的容量和物品的容量的w(i)大小关系
若w(i)>j 则物品不放入
若w(i)<j 则物品有两种选择 :
(1)放入;则需要比较Max【m(i+1,j);m(i+1,j-w(i))+v(i)】取其中的最大值
v(i)为当前你需要放入背包的物品的价值
(2) 不放入,则只需要在相应的位数计算m(i,j)= m(i+1,j)的数值大小进行填充
本题中对于第一行也就是第四个物品所对应的行来说;物品4的重量为7,即所需要的最小的j应该为7 所以对应的7前面的所有数值都为 “0” ,因为背包的容量较小,而所放入的物品的容量过大,大于j的数值,所以为0 ,
同时对于背包容量为7的时候,正好满足w(4)的数值,所以能放入进背包,此时对应的价值为 9 ,填入表中,
而对于基础行来讲,一旦物品放入了,则背包中就满足了4进入了背包,由于之前说到,要明确每一行只是填充一个物品,所以,对于 j==7 之后的背包的价值都为9,按顺序填充即可。
<!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!>
同理第二行,即数字三所对应的行来讲,一样的重复上述操作:
(1)首先看w(3)和j的关系找到最低的要求能放入的对应的“J”,不满足的补充为零,
i/j |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
1 | |||||||||||
2 | |||||||||||
3 | 0 | 0 | 0 | 0 | 5 | ||||||
4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 9 | 9 | 9 | 9 |
(2)查询可知道w(3)=4 所以最低的需要的 “ j ”至少为 4 ,故4之前的都填充为 0
(3)对于4之后的数字需要执行的是与基础行有所不同,此时背包容量满足能放入的条件
故:需要执行Max【m(i+1,j);m(i+1,j-w(i))+v(i)】取其中的最大值 来确定所需要填充的数值,
m(3,4)=m(3+1,4)=0 m(3,4)=m(3+1,4-w(3))+v(3)=m(4,0)+5 = 5
此时m(3,4)中所需要填充的数值为两者中的max数值,所以max=5 故m(3,4)=5
后面的数值则依次执行相应的操作即可 确定m(3,5) 依次填充完对应的“第二行”的数值即可
i/j |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
1 | |||||||||||
2 | |||||||||||
3 | 0 | 0 | 0 | 0 | 5 | 5 | 5 | 9 | 9 | 9 | 9 |
4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 9 | 9 | 9 | 9 |
同理:对于倒数第三行来讲则执行与倒数第二行一样的操作即可
i/j |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
1 | |||||||||||
2 | 0 | 0 | 0 | 3 | 5 | 5 | 5 | 9 | 9 | 9 | 12 |
3 | 0 | 0 | 0 | 0 | 5 | 5 | 5 | 9 | 9 | 9 | 9 |
4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 9 | 9 | 9 | 9 |
此方法中最后的原问题是最右上角的问题,最后的表格为如下图所示
i/j |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
1 | 0 | 0 | 1 | 3 | 5 | 5 | 6 | 9 | 9 | 10 | 12 |
2 | 0 | 0 | 0 | 3 | 5 | 5 | 5 | 9 | 9 | 9 | 12 |
3 | 0 | 0 | 0 | 0 | 5 | 5 | 5 | 9 | 9 | 9 | 9 |
4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 9 | 9 | 9 | 9 |
具体细节如上图所示(前提是执行的为m(i,j)=m(i+1,j))
二.备忘录
“0 1 背包问题中 ”填充的x(i)为是否放入的说明,只有两个默认的数值,一个为“ 0 ” 表示没放入背包
一个为“1”表示放入了背包,比较方法如下:
若m(i,j) == m(i+1,j)数值相同说明没放入背包 ,填入备忘录的数值为 0
若m(i,j) != m(i+1,j)数值相同说明放入背包,填入备忘录的数值为 1
m(i,j) | m(i+1,j) | x(i) |
m(3,7) | m(4,7) | 0 |
m(1,6) | m(2,6) | 1 |
上述表中数值只是为了说明如何进行填充的方法,具体顺序视题目而定
《《》《》《》《》《》《》《《》《》《》《》《》《》《》《》《》《》《》《》《》《》《》《》《》《》《》《》
最后呢:
补充!!!!!!!!!!!!!!!!
而对于网络上很多执行的m(i,j)=m(i-1,j)时候则基础行转为第一行所对应的数值即可,第一行的第一个物品为最小子元素,最右下角为原问题,其他操作与上述方法一样
如果对您有帮助的话请记得点一个关注哦,欢迎您的评论和支持,还在继续更新中。。。。。。
我是楠先生,谢谢您宝贵的意见