《算法设计与分析》实验三 - 实验报告模板

学 号

《算法设计与分析》

实验报告三

学专指成

生业导、

姓班教

名 级 师 绩

计算机与信息工程学院软件工程系

2014 年 10 月 20 日

实验三：贪心算法运用练习

一、实验目的

本次实验是针对贪心算法运用的算法设计及应用练习，旨在加深学生对该部分知识点的理解，提高学生运用该部分知识解决问题的能力。

二、实验步骤与要求

1．实验前复习课程所学知识以及阅读和理解指定的课外阅读材料； 2．学生独自完成实验指定内容；

3．实验结束后，用统一的实验报告模板编写实验报告。

4．提交说明：

（1）电子版提交说明：

a 需要提交Winrar压缩包，文件名为“《算法设计与分析》实验四_学号_姓名”， 如“《算法设计与分析》实验四_09290101_张三”。

b 压缩包内为一个“《算法设计与分析》实验四_学号_姓名”命名的顶层文件夹，

其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验 报告电子版”。其下分别放置对应实验成果物。

（2）打印版提交说明：

a 不可随意更改模板样式。

b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号

字。

c 行间距：单倍行距。

（3）提交截止时间：2014年11月3日16:00。

三、 实验项目

1．传统的找零钱问题的算法及程序实现。

2．特殊的0-1背包问题的求解：本次求解的0-1背包问题的特点为每种物品各有M件，已知每个物品的单位价值，求使得所获价值最大的装包方案。

四、实验过程

1. 算法实现

程序源代码（请写入必要的注释）。 #include using namespace std; int main() {

int a[5]={50,20,10,5,1}; //可以用来找零的钱，以元为单位，不考虑角分

int money;

cout<<\请输入找零钱数：\ cin>>money; int b[100]; int i=0; int j=0;

while(money>0) {

if(money>=a[i]) {

b[j]=a[i];

j++;

money-=a[i]; } else i++; }

cout<<\找回来的零钱：\ for(int x=0;x

#include using namespace std;

void KANPSACK_DP(int c[50][50], int w[50], int v[50], int n, int C) {

for( int i = 0; i <= C; i ++) {

c[0][i] = 0; }

for( i = 1; i <= n; i ++) {

c[i][0] = 0; for(int j = 1; j <= C; j ++) {

if(w[i] <= j) {

if(v[i] + c[i - 1][j - w[i]] > c[i - 1][j]) c[i][j] = v[i] + c[i - 1][j - w[i]]; else c[i][j] = c[i - 1][j]; }

else c[i][j] = c[i - 1][j]; } } }

void OUTPUT_SACK(int c[50][50], int x[50], int w[50], int n, int C) {

for(int k = n; k >= 2; k --) {

if(c[k][C] == c[k-1][C]) x[k] = 0; else { x[k] = 1;

C = C - w[k]; } }

x[1] = c[1][C] ? 1 : 0; } int main()

{

int c[50][50]; int w[50],v[50]; int x[50]; int C,n;

cout<<\输入物品的总个数：\ cin>>n;

cout<<\输入背包的总容量：\ cin>>C;

cout<<\依次输入物品的重量：\ for(int i = 1; i <= n; i ++) {

cin >> w[i]; }

cout<<\依次输入物品的价值：\ for( i = 1; i <= n; i ++) {

cin >> v[i]; }

KANPSACK_DP(c, w, v, n, C);

OUTPUT_SACK(c, x, w, n, C);

cout<<\最优解为：\ for( i = 1; i <= n; i ++) {

cout<

cout<

2. 运行结果

本文来源：https://www.bwwdw.com/article/nubd.html