0-1背包问题-贪心法和动态规划法求解1
- 格式：docx
- 大小：14.99 KB
- 文档页数：6
实验四 “0-1”背包问题
一、 实验目的与要求
熟悉C/C++语言的集成开发环境：
通过本实验加深对贪心算法、动态规划算法的理解。
二、 实验内容：
掌握贪心算法、动态规划算法的概念和基本思想，分析并掌握“0-1”背包问题的求解 方法，并分析貝优缺点。
三、 实验题
1. “0-1”背包问题的贪心算法
2. “0-1”背包问题的动态规划算法
说明：背包实例采用教材P132习题六的6-1中的描述。要求每种的算法都给出最 大收益和最优解。
设有背包问题实例n=7, M=15,, (w0,wl,…w6)= (2, 3, 5, 7,1,4,1),物品装入背 包的收益为:(p0, pl,。。。，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 );
/7获取最优解方法，传入参数为物品收益数组，物品重量数组，最后装载物 品最优解的数组和还可以装载物品的重量
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=GetBestBenif it (p, w, x, M);
cout«endK
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
{
if (arry_avgp[i]
〃交换单位收益数组
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+l]=temp;
//交换重量数组 temp=arry_w[i]; arry_w[i]=arry_w[i+1];
arry_w[i+1]二t emp;
exchange=i;
}
}
}
}
//获取最优解方法，传入参数为物品收益数组，物品重量数组，最后装载物 品最优解的数组和还可以装载物品的重量
float GetBestBenifit (float *arry_p, float *arry_w, float
*arry_x, float u)
{
int i二0; ,7循坏变量i
float benifit=0; //最后收益
while (i<7)
{
if(u~arry_w[i]>0)
{
arry.X[i]=arry_w[i]; //把半前物品重量缴入最优解数
组
benif it+=arry_p[i]; //收益增加前物品收益
u-=arry_w[i]: //背包还能载逼量减去前物品巫
cout«arry_x[i] //输出最优解 } i++；
}
return benifit; //返回最后收益
}
//动态规划法求解
nclude〈>
#include<>
#define n 6
void DKNAP(int p[], int w[], int M, const int m): void
main()
{
int p[n+l], w[n+l];
int M, i, j；
int m^l;
for(i=l;i<=n;i++)
{
m=m*2;
printf C\nin put the weight and the p:〃)； scanf (，z%d %d", &w[i], &p[i]);
)
printf (，z%d/z, m);
printf (，z\n in put the max weight H:〃)；
scanf("%d", &M);
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, 1, h, u, i, j, next, max, s[n+l];
F[0]二1;
p2[l]=w2[l]=0;
l=h=l;
F[l]二next二2;
for(i=l;i
{
k二 1;
max=0;
u 二 1;
for (q=l;q<=h;q++)
if ((w2 [q]+w[i] <=M) &&max<=w2 [q] +w [ i ])
{
u二 q;
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[k]〈ww) {
p2[next]=p2[k];
w2[next]=w2[k];
next++;
k++;
}
辻(k<=h&&w2[k]二二ww)
{
if(pp<=p2[k])
pp二p2 [k];
k++;
}
else if(pp>p2[next-1])
{
p2[next]=pp;
w2[next]=ww;next++;
}
while (k<=h&&p2[k]<=p2[next-1])
k++;
}
while(k<=h)
{
p2[next]=p2[k];
w2[next]二w2[k];
next二next+1; k++;
}
1二h+1;
h二next-1;
F[i+1]二next;
}
for(i=l;i
printf C%2d%2d ", p2[i], w2[i]); for (i=n;i>0;i一一)
next二F[i];
next一一； pp=pk=p2[next];
ww=w2[next]; while (ww+w[i] >M&&next>F[iT])
next=next~l; pp=p2[next]; ww二w2[next];
}
if(ww+w[i]<=M&&next>F[i -1]) px=pp+p[i];
if(px>pk&&ww+w[i]<=M)
{
s[i]二 1; M=M-w[i]; printf (z，M=%d ",
M);
}
else s[i]二0;
)
for (i=l;i<=n;i++)
printf("%2d
",s[i]);
)
六、实验结果
1.贪心法截图:
惯:心袪求解为: 物品总量叢优解知 tali羸续:
七、实验分析
