背包问题资料分享

最近在上工管的算法课,遇到了动态规划解决背包问题,所以网上搜了一下资料,有一份资料对九种背包问题进行了详细介绍,感觉是很好的资料,共16页,在这里分享出来,原创性属于作者本人,本文只是分享一下:
1.  01背包问题
     动态规划;空间复杂度;逆序遍历容量
2.  完全背包问题
     01背包问题化;二进制划分物品;顺序遍历容量
3.  多重背包问题
     01背包问题化;二进制划分物品
4.  混合三种背包问题
     分情况确定遍历顺序
5.  二维费用背包问题
     二维遍历
6.  分组背包问题
     每组物品只能取一个;依次遍历组,组里面遍历每个物品
7.  有依赖背包问题
     主件和所有附件一块组成一组,组内先01背包问题化;分组背包问题
8.  泛化物品
     每个物品是一个数组
9.  其余背包问题问法
     确定最优选择方案;确定所有方案;所有最优方案等等

0 个评论

要回复文章请先登录注册