背包问题贪心法和动态规划法求解.doc

实验四 “0-1”背包问题
实验目与规定
熟悉C/C++语言集成开发环境；
通过本实验加深对贪心算法、动态规划算法理解。
实验内容:
掌握贪心算法、动态规划算法概念和基本思想，分析并掌握“0-1”背包问题求解办法，并分析其优缺陷。
实验题
“0-1”背包问题贪心算法
“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<iostream>
#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 bo