大学讲师,中国首批AP计算机教师,著有中国第一套,历经五年实践证明深受学生欢迎的成功的AP计算机双语教材,2013年以93%的满分率开创了中国AP计算机成功的先河,远远超出全美26.6%的满分率,为中国AP计算机教学树立了典范,并在同年加拿大计算机竞赛中勇夺桂冠,任教学生获哥伦比亚大学,麻省理工学院,卡耐基梅隆大学,宾夕法尼亚大学,康奈尔大学,西北大学等学校录取,远程学生遍及北京、长春、南京、重庆、广州、济南, 深圳、成都、费城,洛杉矶,加州,宾州,新罕布什尔州等地,希望借此平台为信息技术的发展做出贡献！
一．需求分析
（1） 问题描述
已知有n种物品和一个可容纳M重量的背包，每种物品i的重量为W，假定将物
品i的一部分Xi放人背包就会得到PiXi的效益，这里，o≤Xi≤1，Pi>0。采用怎
样的装包方法才会使装入背包物品的总效益最大 。
（2） 建立数学模型
极大化：（1） 
约束条件：（2）
其中，(1)式是目标函数，(2)和(3)是约束条件。满足约束条件的任一集合(x1…xn)是
一个可行解(即能装下)，使目标函数取最大值的可行解是最优解。
（3） 需要测试的数据
考虑下列背包问题：n=3，M=20，(p1，p2，p3)＝(25，24，15)
(w1,w2,w3)＝(18，15，10)。
二．概要设计
（1） 主程序模块
void main( )
{
输入数据；
判断检查；
贪心算法；
输出结果；
}
（2） 检查判断模块
检查数据合法性，不能超过程序预定的最大值 total 。如果输入错误，请重新输
入，输入正确，往下执行
（3） 贪心算法设计
采用在效益值的增长速率和容量的消耗速率之间取得平衡的量度标准，这就需要使
物品的装入次序按pi/wi 比值的费增次序来考虑
Procedure GREEDY_KNAPSACK(P,W,M,X,n)
//P(1:n)和W(1:n) 分别含有按P(i)/W(i)>=P(i+1)/W(i+1)排序的n件物品的效益//值和重量。M是背包的容量大小，而X(1:n)是解向量
real P(1:n),W(1:n),X(1:n),M,cu;
integer i,n;
X←0 //将解向量初始化为0；
cu←M //背包剩余容量
for i←1 to n do
if W(i)>cu then exit endif
X(i)←1
cu←cu-W(i)
repeat
if i<=n then X(i)← cu/W(i)
endif
end GREEDY_KNAPSACK
三．详细设计
（1） 数据类型的定义
//定义全局变量
#define total 10 //物品的最大总数
float p[total],w[total],t[total]; //p[]存储价值，w[]存储重量，t[]辅助数组
float cu; //cu 保存当前背包容量
（2） 数据检查模块
while(1)
{
scanf("%d%f",&n,&cu);
if(n<total) break;
else printf("物品总数超出范围，请重新输入：");
}
（4） 数组的初始化
//t[i]辅助数组，用于标记第i件物品是否被贪心算法所采纳，1表采纳，0表否
for(i=0;i<n;i++)
{
scanf("%f%f",&p[i],&w[i]);
t[i]=0; //初始化为0，表示未采纳
}
（5） 贪心算法的详细设计
//形参，x表示物品数量，c表示当前背包剩余容量
void greedy_knaPsack(int x,int c)
{
int note,i; //note 用于标记最大效益增速物品的下标
float max; //max存储最大效益增速值
while(1)
{
note=0;
max=0;
for(i=0;i<x;i++) //在所有物品里面选择效益增速最大的物品
if((max<p[i]/w[i]) && (t[i]==0))
{
max=p[i]/w[i];
note=i;
}
//如果该物品的重量<背包容量，则被贪心算法采纳，并将t[i]标记为1，//表示已被采纳
if(w[note]<c)
{
t[note]=1;
c-=w[note];
}
else //如果该物品重量小于或者等于背包容量，则取部分
{
t[note]=c/w[note];
break; //退出循坏，表示贪心算法采纳结束
}
}
}
四．调试分析
1．只有一个核心算法，即贪心算法，背包问题，必须在某种度量标准下的最优解才具有意义，因此如何选择度量标准，成为解决该实际问题的关键
2．解决贪心算法问题的基本思路：
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
3. 贪心方法一般伴随着排序，当需要分析的数据量非常大的情况下，选择好的排序方式能大大有效提高程序的执行效率
五．用户手册
（1）本程序的运行环境为DOS操作系统，执行文件为：main.exe
（2）进入演示程序后，即显示文本方式的用户界面，用户只需要按提示输入：
物品的总数与背包容量、物品的质量与效益
、六．测试结果
假设测试数据如下：
n=3，M=20，(p1，p2，p3)＝(25，24，15)，(w1,w2,w3)＝(18，15，10)
计算结果是：
七．附录
| 七．附录 源代码： #include <stdio.h> #define total 10 float p[total],w[total],t[total]; void greedy_knaPsack(int x,int c) { int note,i; float max; while(1) { note=0; max=0; for(i=0;i<x;i++) if((max<p[i]/w[i]) && (t[i]==0)) { max=p[i]/w[i]; note=i; } if(w[note]<c) { t[note]=1; c-=w[note]; } else { t[note]=c/w[note]; break; } } } int main() { int i=0,n=0; float cu; printf("请输入物品总数（不大于%d）与背包的容量：",total); while(1) { scanf("%d%f",&n,&cu); if(n<total) break; else printf("物品总数超出范围，请重新输入："); } printf("请输入每个物品的价值与重量：\n"); for(i=0;i<n;i++) { scanf("%f%f",&p[i],&w[i]); t[i]=0; } greedy_knaPsack(n,cu); printf("由贪心算法所得最优解是：\n"); for(i=0;i<n;i++) printf("%f ",t[i]); return 0; } |
评论