算法实验报告01背包问题.docx

河北工业大学计算机科学与软件学院
算法分析与设计实验
报告
实验：0/1背包问题
姓名:
学号:
班级:
"0-1"背包问题的动态规划算法
一、 实验目的与要求：
熟悉C/C++语言的集成开发环境；
通过本实验加深对i;j++)
{
if(x[j]<x[j + 1])
{
//交换单位价值 p=x[j];
x[j]=x[j + 1];
x[j + 1]=p;
〃交换价值对应位置
vx=v[j];
v[j]=v[j+1];
v[j+1]=vx;
〃交换重量对应位置
wx=w[j];
w[j]=w[j+1];
w[j+1]=wx;
//交换商品编号
m=q[j];
q[j]=q[j + 1];
q[j + 1]=m;
}
}
}
printf("\n单位价值降序为：\n");
for(i=0;i<5;i++)
printf("x[%d]=%d\t”,i,x[i]);
//装入背包
for(i=0;i<n&&w[i]<C;i++)
{
if(w[i]<=C)
{
V+=v[i];
C=C-w[i];
}
}
k=i;
if(C!=0)
{
V+=v[i]*C/w[i];
C=0;
}
for(ii=0;ii<=k;ii++)
{
printf (-\n放入第%d个物品：\n物品的重量为：%d\n物品的价值为：%d\n背包 剩余容量为：
％d\n”,q[ii]+1,w[ii],v[ii],C);
}
printf("\n 总价值为：％d\t”,V);
回
四、实验结果:
■ P%苴法婪敏奇心I「'施bug请心I「,exb
x[l]=10
k[0]=15 x[1]=10 旅入第[个物品： 柳品的重量为，1 瀚心
j<[2]=15
j<[2]=10
6
x[3]=10 xE4]=10
x[3]=10 xE4]=8
0 0
2 2:
-
口 ■■ ■■习・.,■■• 帕为为量 曾旦值容 M重价余 第的的剩 |有
4-
第的的剩
成羽灵H
0曰_值容
4 4 3 : 为. I 口 ■■ ■■
6E Press any key to continue
五、实验分析：
本次实验是以贪心算法解决背包问题，贪心算法要求出每个物 品的单位价值，根据单位价值降序排列，再依次装入背包。当 最后一个物品不能完全装入时，装入部分使背包容量为0。
在本次实验中，遇到几个难题：
保证物品按单位价值排列后依然能知道他的原始顺序位
置，经过几番思考，决定设置一个数组来保存该物品的 原始位置，在冒泡算法交换时同时交换物品编号；
装入背包过程如何保证装入不完整物品，即背包剩余容量
不能满足完全放入下一个物品。
通过本次试验又熟悉了冒泡算法的应用，以及多重for循环的 应用。
一、 实验目的与要求：
熟悉C/C++语言的集成开发环境；
通过本实验加深对贪心算法、动态规划和回溯算法的理解。
二、 实验内容：
掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握"0-1"背包问题的
三种算法，并分析其优缺点。
三、 实验程序：
#include <>
//定义min、max函数
int min(int a,int b)
{
if(a>=b) return b;
else return a;
}
int max(int a,int b)
{
if(a>=b) return a;
else return b;
}
void Knapsack(int v[6],int w[6],int c,int n,int m[6][6])//
{
int jmax=min(w[n]-1,c);
for(int j=0;j<jmax;j++)
m[n][j]=0;
for(int p=w[n];p<=c;p++)
m[n][p]=v[n];
for(int i=n-1;i>1;i--)
{
jmax=min(w[i]-1,c);
for(int j=0;j<=jmax;j++)
m[i][j]=m[i+1][j];
for(int t=w[i];t<=c;t++)
m[i][t]=max(m[i+1][t],m[i+1][t-w[i]]+v[i]);
}
m[1][c]=m[2][c];
if(c>=w[1])
m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
}
void Traceback(int m[6][6],int w[6],int c,int n,i