背包问题.ppt

《背包问题.ppt》由会员分享，可在线阅读，更多相关《背包问题.ppt（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、背包问题背包问题部分背包问题 有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但重量不能超过总容量。物品 ABCDEFG重量35306050401025价值10403050354030（3）每次选取单位容量价值最大的物品，成为解本题的策略。分析：目标函数：pi最大约束条件是装入的物品总重量不超过背包容量：wi=M(M=150)（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？（2）每次挑选所占空间最小的物品装入是否能得到最优解？0-1背包问题 问题描述：给定 n 种物品和一背包。物品 i 的重量是 wi，其价

2、值为 pi，背包的容量为 m。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？（物品不能切割）输入：输入数据共有 n 行，第一行有一个实数 m和一个整数 n，分别为背包容量和物品数。接下来有 n 行，每行有两个实数，分别为背包 i 的重量和价值 输出：数出数据只有一个实数，它表示最大的总价值。例子输入例子输入10 3 8 10 3 8 3 8例子输出例子输出16fij表示前i件物品放入一个容量为j的背包可以获得的最大价值。(注：i件物品不一定全部放入背包）“将前i件物品放入容量为j的背包中”这个子问题若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为j的背包中”，价值为fi-1j；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为j-wi的背包中”，此时能获得的最大价值就是fi-1j-wi再加上通过放入第i件物品获得的价值pi。fij=max fi-1j,fi-1j-wi+pi 先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1.n，每次算出来二维数组fi0.M的所有值。fij是由fi-1j和fi-1j-wi两个子问题递推而来伪代码如下：for i=1.n for j=0.M fij=maxfi-1j,fi-1j-wi+pi;