算法导论中科大算法导论_实验二__背包问题资源-CSDN文库

需积分: 10 111 浏览量 2015-12-18 19:38:32 上传评论收藏 78KB DOC 举报

资源推荐

资源详情

资源评论

实验二背包问题

1. 问题描述:

编程实现 0-1 背包问题，部分背包问题

2. 算法原理:

 0-1 背包问题

01 背包是在 M 件物品取出若干件放在空间为 W 的背包里，每件物品的体积为

W1，W2……Wn，与之相对应的价值为 P1,P2……Pn。

考虑用动态规划的方法来解决，这里的：

阶段是：在前 N 件物品中，选取若干件物品放入背包中；

状态是：在前 N 件物品中，选取若干件物品放入所剩空间为 W 的背包中的所能获

得的最大价值；

决策是：第 N 件物品放或者不放；

由此可以写出动态转移方程：

我们用 f[i,j]表示在前 i 件物品中选择若干件放在所剩空间为 j 的背包里所能获得的

最大价值

f[i, j] = max( f[i-1, j-Wi] + Pi (j >= Wi), f[i-1, j] )

 部分背包问题

给定 n 种物品和一个背包。物品 i 的重量是 Wi，其价值为 Vi，背包的容量为 C。

应如何选择装入背包的物品，使得装入背包中物品的总价值最大

选择物品 i 装入背包时，可以选择物品 i 的一部分，而不一定要全部装入背包，

1≤i≤n。

因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以

它局部最优满足全局最优，可以用贪心法解决。

首先计算每种物品单位重量的价值 V/W，然后按单位重量价值从大到小进行排序，

根据贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。或将这种物品

全部装入背包后，背包内的物品总重量未超过背包容量，则选择单位重量价值次高的

物品并尽可能多地装入背包，依此策略一直进行下去，直到背包装满为止。

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余7页未读，立即下载

内容反馈

汤大帅哥

粉丝: 0
资源: 3

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip