贪心算法试题

第八章 贪心算法 一、选择题

1 用贪心法设计算法的关键是（ D）。

A．将问题分解为多个子问题来分别处理 B．选好贪心准则 C．获取各阶段间的递推关系式 D．满足最优性原理

2 考虑背包问题：n=6，M=10，P(1:6)=(15,59,21,30,60,5)，W(1:6)=(1,5,2,3,6,1）。该问题的最大效益值为（B）。若把它看着是0/1 背包问题，则最大效益值为（C）。 A．101 B．110 C．115 D．120

8.3#include

int main() {

freopen(\

int money,s1,s2,s3,s4,s5,p,d,n,q,h,temp;

scanf(\

temp=money;

p = money/s1;

if (p >0)

money -= p*s1;

d = money/s2;

if (d >0)

money -= d*s2;

n = money/s3;

if (n >0)

money -= n*s3;

q = money/s4;

自 然 计 算 概 论（论文）

题 目：对贪心算法的认识

学生姓名：丁子颢

号：2015030202028 院：微电子与固体电子学院

2016年6月7日

学学专业班级：集成电路设计与集成系统二班

摘 要

在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。本文讲述了贪心算法的含义、基本思路及实现过程，贪心算法的核心、基本性质、特点及其存在的问题。并通过贪心算法的特点举例列出了以往研究过的几个经典问题，对于实际应用中的问题，也希望通过贪心算法的特点来解决。

关键词：贪心算

第八章 贪心算法 一、选择题

1 用贪心法设计算法的关键是（ D）。

A．将问题分解为多个子问题来分别处理 B．选好贪心准则 C．获取各阶段间的递推关系式 D．满足最优性原理

2 考虑背包问题：n=6，M=10，P(1:6)=(15,59,21,30,60,5)，W(1:6)=(1,5,2,3,6,1）。该问题的最大效益值为（B）。若把它看着是0/1 背包问题，则最大效益值为（C）。 A．101 B．110 C．115 D．120

8.3#include

int main() {

freopen(\

int money,s1,s2,s3,s4,s5,p,d,n,q,h,temp;

scanf(\

temp=money;

p = money/s1;

if (p >0)

money -= p*s1;

d = money/s2;

if (d >0)

money -= d*s2;

n = money/s3;

if (n >0)

money -= n*s3;

q = money/s4;

实验三 贪心算法

基本题一：多机调度问题 一、实验目的与要求

1、熟悉多机调度问题的算法； 2、初步掌握贪心算法； 二、实验题

要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。 三、实验提示

1、把作业按加工所用的时间从大到小排序

2、如果作业数目比机器的数目少或相等，则直接把作业分配下去

3、 如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上s最小的链表加入新作业。 # include # include using namespace std;

typedef struct Job //作业 {

int ID; int time; }Job;

typedef struct JobNode //作业链表的节点 {

int ID; int time;

JobNode *next; }JobNode,*pJobNode;

typedef struct Header //链表的表头 {

int s

北京联合大学应用文理学院

北京联合大学应用文理学院

实验（实训报告）

课程名称 算法分析与程序设计

实验（实训）名称 实验三 贪心算法

班级 07信息 组别 姓名

同组者

实验（实训）日期 2010.11.28 完成日期 2010.11.29

本实验（实训）所用学时统计

预习 1 实验（实训） 2 报告 1 总计 4

评阅意见： 成绩

北京联合大学应用文理学院

北京联合大学应用文理学院

实 验 报 告

专业：信息与计算科学 班级： 2008 姓名： 学号： 2008010301018

一．课程设计名称：

删数问题

二.实验内容 问题描述:

键盘输入一个高精

贪心算法求解背包问题

一、 实验内容

有一个承重为W的背包和n个物品，它们各自的重量和价值分别是wi和vin

W wi求这些物品中最有价值的一个子集。如果每次选择某（1<=i<=n），设

i 1一个物品的时候，只能全部拿走，则这一问题称为离散（0-1）背包问题；如果每次

可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。

二、 算法思想

首先计算出物品单位重量的价值vi/wi，并排序，依贪婪策略，从物品中选择可装入背包的vi/wi值最大的物品。若该物品装入背包后，背包中物品总重量未超过背包最大承重m，则选择单位重量价值次之的物品装入背包，依次策略进行下去，直到背包装满为止。

三、 实验过程（C++）

#include<iostream>

using namespace std;

//n表示背包可以存放物品的种类

//指针p指向存放物品价值的数组

//指针q指向存放物品重量的数组

void sort(int n,float *p,float *q)

{

int i;

int j;

for(i=0;i<n-1;i++)

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

if((*(p+i))/(*(q+i))<(*(p+j))/(*(q+j)))

。

计算机算法设计与分析（第3版）

128页

算法实现题4-1 会场安排问题

问题描述：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。) 编程任务：对于给定的k 个待安排的活动，编程计算使用最少会场的时间表。Input 输入数据是由多组测试数据组成。每组测试数据输入的第一行有1 个正整数k，表示有k 个待安排的活动。接下来的k 行中，每行有2 个正整数，分别表示k 个待安排的活动开始时间和结束时间。时间以0 点开始的分钟计。Output 对应每组输入，输出的每行是计算出的最少会场数。

源代码：

#include

int fnPartition(int a[], int low, int high)

{

int i,j;

int x = a[low];

i = low;

j = high;

while(i

{

-可编辑修改-

。

while(i { j = j-1; }

if(i

while(i =a[i]) i++;

if(i

}

a[i] = x;

return i;

}

void fnQu

贪心算法求解背包问题

一、 实验内容

有一个承重为W的背包和n个物品，它们各自的重量和价值分别是wi和vin

W wi求这些物品中最有价值的一个子集。如果每次选择某（1<=i<=n），设

i 1一个物品的时候，只能全部拿走，则这一问题称为离散（0-1）背包问题；如果每次

可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。

二、 算法思想

首先计算出物品单位重量的价值vi/wi，并排序，依贪婪策略，从物品中选择可装入背包的vi/wi值最大的物品。若该物品装入背包后，背包中物品总重量未超过背包最大承重m，则选择单位重量价值次之的物品装入背包，依次策略进行下去，直到背包装满为止。

三、 实验过程（C++）

#include<iostream>

using namespace std;

//n表示背包可以存放物品的种类

//指针p指向存放物品价值的数组

//指针q指向存放物品重量的数组

void sort(int n,float *p,float *q)

{

int i;

int j;

for(i=0;i<n-1;i++)

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

if((*(p+i))/(*(q+i))<(*(p+j))/(*(q+j)))

计算机与信息科学学院2010-2011学年第2学期模拟试卷

计算机算法设计与分析—第四章.贪心算法

本卷满分100分 完卷时间120分钟

一. 简答题（每小题2分，共20分）

1. 当一个问题具有 且具有 时可用贪心算法，如最小生成树问题（背包问题，活动安排问题等）。

2. 在动态规划可行的基础上满足 才能用贪心。

3. 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的 选择。 4. 动态规划算法通常以 的方式解各子问题，而贪心算法则通常 以 的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题

5. 贪心算法和动态规划算法都要求问题具有 性质，这是2类算法的一个共同点。

6. 当一个问题的最优解包含其子问题的最优解时，称此问题具有 。 7. 对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这

(n)时间。这个循环需要执行个图，那么Dijkstra算法的主循环体需要O

n-1次，所以完成循环需要

淮海工学院计算机工程学院

实验报告书

课程名： 《算法分析与设计》 题 目： 实验3 贪心算法

哈夫曼编码

班 级： 软件081班 学 号： 110831116 姓 名： 陈点点

评语： 成绩： 指导教师： 批阅时间： 年 月 日 《 算法分析与设计》实验报告 - 1 -

实验3 贪心算法

实验目的和要求

（1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用 （4）证明哈夫曼树满足最优子结构性质； （5）设计贪心算法求解哈夫曼编码方案； （6）设计测试数