用蛮力法、动态规划法和贪心法求解0-1背包问题

实验项目三实验项目三 用蛮力法 动态规划法和贪心法求解用蛮力法 动态规划法和贪心法求解 0 1 背包问题背包问题 实验目的实验目的 1 学会背包的数据结构的设计 针对不同的问题涉及到的对象的数据结构的设计也 不同 2 对 0 1 背包问题的算法设计策略对比与分析 实验内容 实验内容 0 1 背包问题是给定 n 个重量为 w1 w2 wn 价值为 v1 v2 vn 的物品和一个 容量为 C 的背包 求这些物品中的一个最有价值的子集 并且要能够装到背包中 在 0 1 背包问题中 物品 i 或者被装入背包 或者不被装入背包 设 xi 表示物品 i 装 入背包的情况 则当 xi 0 时 表示物品 i 没有被装入背包 xi 1 时 表示物品 i 被装入背 包 根据问题的要求 有如下约束条件和目标函数 1 1 0 1 nix Cxw i n i ii 式1 n i iix v 1 max 式2 于是 问题归结为寻找一个满足约束条件式 1 并使目标函数式 2 达到最大的解向量 X x1 x2 xn 背包的数据结构的设计 typedef struct object int n 物品的编号 int w 物品的重量 int v 物品的价值 wup wup wp N 物品的数组 N 为物品的个数 int c 背包的总重量 1 蛮力法 蛮力法 蛮力法是一种简单直接的解决问题的方法 常常直接基于问题的描述和所涉及的概念 定义 蛮力法的关键是依次处理所有的元素 用蛮力法解决 0 1 背包问题 需要考虑给定 n 个物品集合的所有子集 找出所有可能 的子集 总重量不超过背包容量的子集 计算每个子集的总价值 然后在他们中找到价值 最大的子集 所以蛮力法解 0 1 背包问题的关键是如何求 n 个物品集合的所有子集 n 个物品的子集 有 2 的 n 次方个 用一个 2 的 n 次方行 n 列的数组保存生成的子集 以下是生成子集的算 法 void force int a 4 蛮力法产生 4 个物品的子集 int i j int n 16 int m t for i 0 i 0 j m t 2 a i j m t t 2 for i 0 i 16 i 输出保存子集的二维数组 for j 0 j 4 j printf d a i j printf n 以下要依次判断每个子集的可行性 找出可行解 void panduan int a 4 int cw 判断每个子集的可行性 如果可行则计算其价值存入 数组 cw 不可行则存入 0 int i j int n 16 int sw sv for i 0 i 16 i sw 0 sv 0 for j 0 j 4 j sw sw wp j w a i j sv sv wp j v a i j if sw c cw i sv else cw i 0 在可行解中找出最优解 即找出可行解中满足目标函数的最优解 以下是找出最优解 的算法 int findmax int x 16 4 int cv 可行解保存在数组 cv 中 最优解就是 x 数组中某行的 元素值相加得到的最大值 int max int i j max 0 for i 0 imax max cv i j i printf n 最好的组合方案是 for i 0 i 4 i printf d x j i return max 2 动态规划法 动态规划法 动态规划法将待求解问题分解成若干个相互重叠的子问题 每个子问题对应决策过程 的一个阶段 一般来说 子问题的重叠关系表现在对给定问题求解的递推关系 也就是动 态规划函数 中 将子问题的解求解一次并填入表中 当需要再次求解此子问题时 可以 通过查表获得该子问题的解而不用再次求解 从而避免了大量重复计算 动态规划法设计算法一般分成三个阶段 1 分段 将原问题分解为若干个相互重叠的子问题 2 分析 分析问题是否满足最优性原理 找出动态规划函数的递推式 3 求解 利用递推式自底向上计算 实现动态规划过程 0 1 背包问题可以看作是决策一个序列 x1 x2 xn 对任一变量 xi 的决策是决定 xi 1 还是 xi 0 在对 xi 1 决策后 已确定了 x1 xi 1 在决策 xi 时 问题处于下列两种 状态之一 1 背包容量不足以装入物品 i 则 xi 0 背包不增加价值 2 背包容量可以装入物品 i 则 xi 1 背包的价值增加了 vi 这两种情况下背包价值的最大者应该是对 xi 决策后的背包价值 令 V i j 表示在前 i 1 i n 个物品中能够装入容量为 j 1 j C 的背包中的物品的最大值 则可以得到如 下动态规划函数 V i 0 V 0 j 0 式 式 3 式 4 式 3 表明 把前面 i 个物品装入容量为 0 的背包和把 0 个物品装入容量为 j 的背包 得到的价值均为 0 式 4 的第一个式子表明 如果第 i 个物品的重量大于背包的容量 则装 入前 i 个物品得到的最大价值和装入前 i 1 个物品得到的最大价值是相同的 即物品 i 不能 装入背包 第二个式子表明 如果第 i 个物品的重量小于背包的容量 则会有以下两种情 况 1 如果把第 i 个物品装入背包 则背包中物品的价值等于把前 i 1 个物品装入容量 为 j wi 的背包中的价值加上第 i 个物品的价值 vi 2 如果第 i 个物品没有装入背包 则 背包中物品的价值就等于把前 i 1 个物品装入容量为 j 的背包中所取得的价值 显然 取二 者中价值较大者作为把前 i 个物品装入容量为 j 的背包中的最优解 以下是动态规划法求解背包问题的算法 int findmaxvalue wup p int x x 数组用来存放可行解 p 是指向存放物品数组的指针 int i j int maxvalue int value N 1 C 1 for j 0 j C j value 0 j 0 初始化第 0 行 for i 0 i N i value i 0 0 初始化第 0 列 计算数组 value 中各元素的值 for i 1 i N i p for j 1 jw j value i j value i 1 j else value i j max value i 1 j value i 1 j p w p v max 函数求两 个数当中的大者 逆推求解 j C for i N i 0 i if value i j value i 1 j iii i wjvwjiVjiV wjjiV jiV 1 1 max 1 x i 1 1 是否被选中的向量的下标也是从 0 开始 j j wp i 1 w 存放物品的下标从 0 开始 else x i 1 0 maxvalue value N C 最大值 return maxvalue 3 贪心法 贪心法 贪心法在解决问题的策略上目光短浅 只根据当前已有的信息就做出选择 而且 一旦做出了选择 不管将来有什么结果 这个选择都不会改变 换言之 贪心法并不是从 整体最优考虑 它所做出的选择只是在某种意义上的局部最优 这种局部最优选择并不总能获得整体最优解 Optimal Solution 但通常能获得近 似最优解 Near Optimal Solution 贪心法求解的问题的特征 贪心法求解的问题的特征 1 最优子结构性质 当一个问题的最优解包含其子问题的最优解时 称此问题具有最优子结构性 质 也称此问题满足最优性原理 2 贪心选择性质 所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择 即贪心选择来得到 用贪心法求解问题应该考虑如下几个方面 1 候选集合 C 为了构造问题的解决方案 有一个候选集合 C 作为问题的可能解 即问题的最终解均取自于候选集合 C 例如 在付款问题中 各种面值的货币构成候选集 合 2 解集合 S 随着贪心选择的进行 解集合 S 不断扩展 直到构成一个满足问题的 完整解 例如 在付款问题中 已付出的货币构成解集合 3 解决函数 solution 检查解集合 S 是否构成问题的完整解 例如 在付款问题中 解决函数是已付出的货币金额恰好等于应付款 4 选择函数 select 即贪心策略 这是贪心法的关键 它指出哪个候选对象最有希 望构成问题的解 选择函数通常和目标函数有关 例如 在付款问题中 贪心策略就是在 候选集合中选择面值最大的货币 5 可行函数 feasible 检查解集合中加入一个候选对象是否可行 即解集合扩展后 是否满足约束条件 例如 在付款问题中 可行函数是每一步选择的货币和已付出的货币 相加不超过应付款 背包问题至少有三种看似合理的贪心策略 1 选择价值最大的物品 因为这可以尽可能快地增加背包的总价值 但是 虽 然每一步选择获得了背包价值的极大增长 但背包容量却可能消耗得太快 使得装入背包 的物品个数减少 从而不能保证目标函数达到最大 2 选择重量最轻的物品 因为这可以装入尽可能多的物品 从而增加背包的总 价值 但是 虽然每一步选择使背包的容量消耗得慢了 但背包的价值却没能保证迅速增 长 从而不能保证目标函数达到最大 3 选择单位重量价值最大的物品 在背包价值增长和背包容量消耗两者之间寻 找平衡 应用第三种贪心策略 每次从物品集合中选择单位重量价值最大的物品 如果其重量 小于背包容量 就可以把它装入 并将背包容量减去该物品的重量 然后我们就面临了一 个最优子问题 它同样是背包问题 只不过背包容量减少了 物品集合减少了 因此背 包问题具有最优子结构性质 先按单位重量价值最大对物品进行排序 然后再用贪心策略选择的算法如下 float find float p N float w N float x N float M int n 先放单位价值量大的物体 再 考虑小的物体 int i float maxprice for i 0 i n i x i 0 i 0 maxprice 0 while i n x i w i 表示放入数量 maxprice maxprice p i x n 1 M i if i 0 maxprice maxprice p i x i w i i return maxprice include include include define C 10 定义背包总重量为 10 define N 4 定义物品个数为 4 typedef struct object 背包的数据结构的设计 int n 物品的编号 int w 物品的重量 int v 物品的价值 wup wup wp N 物品的数组 N 为物品的个数 void inputwp wup p 输入函数 int i i 为物品的个数 for i 0 in 输入物品的编号 scanf d 输入物品的重量 scanf d 输入物品的价值 p p 1 p 为一个指针 指向下一个物品 printf n 输出结果 void ontputwp wup p 输出函数 int i i 为物品的个数 for i 0 in p w p v 把物品的编号 重量 价值和起来输 出给 i 个物品 p p 1 指针指向下一个物品 printf n 输出结果 float find float y N float w N float x N float M int n 先放单位价值量大的物体 再 考虑小的物体 int i float maxprice for i 0 i n i x i 0 i 0 maxprice 0 while i n x i w i 表示放入数量 maxprice maxprice y i x n 1 M i if i 0 maxprice maxprice y i x i w i i return maxprice void main wup p 这是一个 wup 型的指针 p float y N float w N float