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

实验四 0 1 背包问题 一 一 实验目的与要求实验目的与要求 熟悉 C C 语言的集成开发环境 通过本实验加深对贪心算法 动态规划算法的理解 二 二 实验内容实验内容 掌握贪心算法 动态规划算法的概念和基本思想 分析并掌握 0 1 背包问题的求解 方法 并分析其优缺点 三 三 实验题实验题 1 0 1 背包问题的贪心算法 2 0 1 背包问题的动态规划算法 说明 背包实例采用教材 P132 习题六的 6 1 中的描述 要求每种的算法都给出最大收 益和最优解 设有背包问题实例 n 7 M 15 w0 w1 w6 2 3 5 7 1 4 1 物品装入 背包的收益为 p0 p1 p6 10 5 15 7 6 18 3 求这一实例的最优解和 最大收益 四 四 实验步骤实验步骤 理解算法思想和问题要求 编程实现题目要求 上机输入和调试自己所编的程序 验证分析实验结果 整理出实验报告 五 五 实验程序实验程序 贪心法求解 include include iomanip using namespace std 按照单位物品收益排序 传入参数单位物品收益 物品收益和物品重量的数 组 运用冒泡排序 void AvgBenefitsSort float arry avgp float arry p float arry w 获取最优解方法 传入参数为物品收益数组 物品重量数组 最后装载物品 最优解的数组和还可以装载物品的重量 float GetBestBenifit float arry p float arry w float arry x float u int main float w 7 2 3 5 7 1 4 1 物品重量数组 float p 7 10 5 15 7 6 18 3 物品收益数组 float avgp 7 0 单位毒品的收益数组 float x 7 0 最后装载物品的最优解数组 const float M 15 背包所能的载重 float ben 0 最后的收益 AvgBenefitsSort avgp p w ben GetBestBenifit p w x M cout endl ben endl 输出最后的收益 system pause return 0 按照单位物品收益排序 传入参数单位物品收益 物品收益和物品重量的数 组 运用冒泡排序 void AvgBenefitsSort float arry avgp float arry p float arry w 求出物品的单位收益 for int i 0 i 7 i arry avgp i arry p i arry w i cout endl 把求出的单位收益排序 冒泡排序法 int exchange 7 int bound 0 float temp 0 while exchange bound exchange exchange 0 for int i 0 i bound i if arry avgp i arry avgp i 1 交换单位收益数组 temp arry avgp i arry avgp i arry avgp i 1 arry avgp i 1 temp 交换收益数组 temp arry p i arry p i arry p i 1 arry p i 1 temp 交换重量数组 temp arry w i arry w i arry w i 1 arry w i 1 temp exchange i 获取最优解方法 传入参数为物品收益数组 物品重量数组 最后装载物品 最优解的数组和还可以装载物品的重量 float GetBestBenifit float arry p float arry w float arry x float u int i 0 循环变量i float benifit 0 最后收益 while i0 arry x i arry w i 把当前物品重量缴入最优解数组 benifit arry p i 收益增加当前物品收益 u arry w i 背包还能载重量减去当前物品重量 cout arry x i 输出最优解 i return benifit 返回最后收益 动态规划法求解 include include define n 6 void DKNAP int p int w int M const int m void main int p n 1 w n 1 int M i j int m 1 for i 1 i n i m m 2 printf nin put the weight and the p scanf d d printf d m printf n in put the max weight M scanf d DKNAP p w M m void DKNAP int p int w int M const int m int p2 m w2 m pp ww px int F n 1 pk q k l h u i j next max s n 1 F 0 1 p2 1 w2 1 0 l h 1 F 1 next 2 for i 1 i n i k l max 0 u l for q l q h q if w2 q w i M max w2 q w i for j l j u j pp p2 j p i ww w2 j w i while k h w2 next w2 k next k if k h w2 next ww next while k h while k h p2 next p2 k w2 next w2 k next next 1 k l h 1 h next 1 F i 1 next for i 1 i0 i next F i next pp pk p2 next ww w2 next while ww w i M pp p2 next ww w2 next if