《算法设计与分析》实验报告五
学号： 1004091130
日期： 2011-11-10
一、 实验内容：
应用贪心算法求解背包问题 姓名： 金玉琦 得分：
二、所用算法的基本思想及复杂度分析：
1.贪心法
贪心法是把一个复杂问题分解为一系列较为简单的局部最优选择, 每一步选择都是对当前解的一个扩展, 直到获得问题的完整解。贪心法的典型应用是求解最优化问题, 而且对许多问题都能得到整体最优解, 即使不能得到整体最优解, 通常也是最优解的很好近似。
背包问题
1） 基本思想
给定n 种物品和一个容量为C 的背包, 物品i 的重量是w, 价值为v, 背包问题是如何i i
选择装入背包的物品, 使得装入背包中物品的总价值最大。有3 种看似合理的贪心策略： (1 ) 选择价值最大的物品, 因为这可以尽可能快地增加背包的总价值。但是, 虽然每一
步选择获得了背包价值的极大增长, 但背包容量却可能消耗得太快, 使得装入背包的物品个数减少, 从而不能保证目标函数达到最大。
(2 ) 选择重量最轻的物品, 因为这可以装入尽可能多的物品, 从而增加背包的总价值。但是, 虽然每一步选择使背包的容量消耗得慢了, 但背包的价值却没能保证迅速增长, 从而不能保证目标函数达到最大。
(3 ) 以上两种贪心策略或者只考虑背包价值的增长, 或者只考虑背包容量的消耗, 而为了求得背包问题的最优解, 需要在背包价值增长和背包容量消耗两者之间寻找平衡。正确的贪心策略是选择单位重量价值最大的物品。
应用第3 种贪心策略, 每次从物品集合中选择单位重量价值最大的物品, 如果其重量小于背包容量, 就可以把它装入, 并将背包容量减去该物品的重量, 然后我们就面临了一个最优子问题———它同样是背包问题, 只不过背包容量减少了, 物品集合减少了。因此背包问题具有最优子结构性质。
2）复杂度分析
算法的时间主要消耗在将各种物品依其单位重量的价值从大到小排序。因此,算法其时间复杂性为O( nlog2 n)。
三．源程序及注释：
#define MAX 100
#include <TIME.H>
#include <IOSTREAM>
1
#include <algorithm>
using namespace std;
//设计物品属性，重量和价值
struct Things
{
double w; //记录重量
double v; //记录价值
};
//按单位价值降序排列
int cmp(Things a,Things b)
{
return a.v/a.w>b.v/b.w;
}
//贪心法背包问题函数
double Bag_Value(Things a[],int c,int n)
{
double bag_val1=0,bag_val2=0;
int i=0;
double weight_sum=0;
for(int j=0;j<n;j++) //求出所有物品的重量和
{
weight_sum+=a[j].w;
bag_val2+=a[j].v;
}
if(weight_sum<=c) //所有物品小于容量，直接输出结果 {
cout<<"将所有物品放入背包"<<endl;
return bag_val2;
}
else //重量和大于背包容量，贪心法求解 {
sort(a,a+n,cmp);
while(a[i].w<=c)
{
if(a[i].w<=c)
{
c=c-a[i].w;
bag_val1+=a[i].v;
cout<<"价值为"<<a[i].v<<"的物品放入"
<<a[i].w<<endl;
}
2
i++;
}
if(c)
{
cout<<"价值为"<<a[i].v<<"的物品放入"<<c<<endl; bag_val1+=a[i].v/a[i].w*c;
}
return bag_val1;
}
}
void main()
{
Things t[MAX];
int i,n,c;
int result;
cout<<"输入物品总数:";
cin>>n;
cout<<"输入背包的总容量:";
cin>>c;
srand(time(0));
for (i=0;i<n;i++)
{
t[i].w=rand()/55;
t[i].v=rand()/55;
cout<<"第"<<i+1<<"个物品重量:"<<t[i].w
<<" 价值:"<<t[i].v<<endl;
}
cout<<"结果"<<endl;
result=Bag_Value(t,c,n);
cout<<"背包总价值:"<<result<<endl;
}
四、运行输出结果：
3
五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：
背包问题与0/ 1 背包问题类似,这两类问题都具有最优子结构性质, 所不同的是背包问题在选择物品装入背包时, 可以选择一部分, 而不一定要全部装入背包,而对于0/ 1 背包问题却不能用贪心法求解，是由于物品不允许分割，因此,无法保证最终能将背包装满。所以，在编写程序的时候需要特别注意这个问题。
4
第二篇：兴-贪心背包
算法设计与分析实验报告 专 业：
学 号：
姓 名：
指导老师：宋胜利
软件测试技术0901 540913110130 沈运兴 李璞
实验三：贪心算法 背包问题
一、实验目的与要求
1、掌握背包问题的算法
2、初步掌握贪心算法
二、实验题：
问题描述：与0-1背包问题相似，给定n种物品和一个背包。物品i的重量是weight[i]，其价值为profit[i]，背包的容量为contain。与0-1背包问题不同的是，在选择物品i装入背包时，背包问题的解决可以选择物品i的一部分，而不一定要全部装入背包，1< i < n。 #include "iostream"
#define n 50 //物品的数量
//物体重量、收益、背包容量
int weight[n], profit[n], contain,number; //物体的单位重量价值
float pervalues[n], x[n];
//从文件中读取背包信息
int read_infor()
{
FILE *fp;
int i;
if
((fp=fopen("knapsack.txt","r"))==NULL) {
printf("The file is not found!");
return 0;
}
fscanf(fp,"%d",&number);
printf("背包数量是%d\n",number); //读取物体收益信息
for(i = 0;i < number;i++)
{
fscanf(fp, "%d", &profit[i]);
printf("第%d个物品的收益是%d\n",i+1,profit[i]);
}
//读取物体重量信息，计算物体的单位重量价值
for(i = 0;i < number;i++)
{
fscanf(fp, "%d", &weight[i]);
printf("第%d个物品的重量是%d\n",i+1,weight[i]);
pervalues[i] = profit[i] / (float)weight[i];
}
//读取背包容量
fscanf(fp, "%d", &contain);
printf("背包容量是%d\n",contain); fclose(fp);
return 1;
}
void sort()
{
int i, j, max, tmp;
float ftmp;
for(i = 0;i < number;i++)
{
max = i;
for(j = i + 1;j < number;j++) {
if(pervalues[max] < pervalues[j]) {
max = j;
}
}
ftmp = pervalues[i];
pervalues[i] = pervalues[max];
pervalues[max] = ftmp;
tmp = weight[i];
weight[i] = weight[max]; weight[max] = tmp;
tmp = profit[i];
profit[i] = profit[max]; profit[max] = tmp; }
}
void Knapsack()
{
int i, c = contain;
for(i = 0;i < number;i++) {
x[i] = 0;
}
for(i = 0;i < number;i++) {
if(weight[i] > c)
{
break;
}
x[i] = 1;
c -= weight[i];
}
if(i < n)
{
x[i] = c / (float)weight[i]; }
}
void main()
{
int i;
float sumWeight = 0, sumProfit = 0; if(read_infor())
{
sort();
Knapsack();
for(i = 0;i < number;i++) {
sumWeight += weight[i] * x[i];
sumProfit += profit[i] * x[i]; }
printf("最大收益是: %f.", sumProfit); printf("\n背包总重量 %f.\n", sumWeight);
}
scanf("%d", &i);
}
运行例子：在程序的相同目录下创建knapsack.txt。依次写入3 3 5 8 10 5 9 20，其中黑色数字代表物品个数，红色数字代表收益，蓝色数字代表重量，橙色代表背包容量；
