贪心算法汽车加油问题
1. PASCAL贪心算法，汽车行驶加油问题
http://hi..com/samroxas/item/d775f2c0b2f79c0aad092f0e
这是我曾经写的结题报告，基本一样的题目，相信会对你有帮助。
2. 汽车加油问题 贪心算法（C++）
第一次加满油
然后在能到达的最远的加油站再加满油
如此反复, 最后到达目的地
如果中间某次加油后不能到达下面任何一个加油站
那么就无解
3. 关于一道c语言的加油站选择问题，用贪心算法
需要贪心算法吗？
如果途径线路是固定的：
只需汽车经过某个加油站，剩余油量不够支撑到下个加油站，那么就在这个加油站加油。
你要做这些系统，那么一些基本数值是必须的。
1。油箱容积。
2。百公里油耗。
3。加油站间距离。
4. 求贪心算法汽车加油问题程序
#include<iostream.h>
#include<fstream.h>配键
void addoil(int &n,int &k,int *a,int *c,bool *b1,bool *b2,int &count)
{
int oil=n;
//count=0;
int i=0;
//a=new int[k+1];
b1=new bool[k+1];
c=new int[k+1];
b2=new bool[k+1];
while(i<=k)
{
if(oil-a[k]<a[k+1])
{
oil=n;
count++;
c[k]=k;
b1[k]=true;
}
if(a[k]>n)
{
b2[k]=false;
break;
}
if(oil-a[k]>a[k+1] && a[k]<=n)
i++;
}
}
void main()
{
int n,k;
int count=0;
int *a,*c;
bool *b1,*b2;
ifstream fin;
fin.open("D:\\input.txt");
fin>>n>>k;
a=new int[k+1];
b1=new bool[k+1];
c=new int[k+1];
b2=new bool[k+1];
for(int i=0;i<k+1;i++)
fin>>a[i];
addoil(n,k,a,c,b1,b2,count);
ofstream fout("D:\\output.txt");
for(int j=0;j<k+1;j++)
if(b2[j]=false)
{
fout<培谨巧<晌弯"No Solution";
return;
}
for(int l=0;l<k+1;l++)
if(b1[l]=true)
{
fout<<"should add oil at the "<<c[k]<<"service station"<<endl;
}
fout<<count;
}
5. 应用问题求解，加油站有效加油位问题！
1.已知有
3
个物品：(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积
M=20，根据
0-1
背
包动态规划的递推式求出最优解。
2.按要求完成以下关于排序和查找的问题。
①对数组
A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。
②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。
③给出上述算法的递归算法。
④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。
3.已知
1
(
)
*
(
)
i
i
k
k
ij
r
r
A
a
+
=
，
k
=1，2，3，4，5，6，
r
1
=5，
r
2
=10，
r
3
=3，
r
4
=12，
r
5
=5，
r
6
=50，
r
7
=6，
求矩阵链积
A
1
×A
2
×A
3
×A
4
×A
5
×A
6
的最佳求积顺序（要求给出计算步骤）
。
4.
根
据
分
枝
限
界
算
法
基
本
过
程
,
求
解
0-1
背
包
问
题
。
已
知
n=3,M=20
，
(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。
5.试用贪心算法求解汽车加油问题：
已知一辆汽车加伏没满油后可行驶
n
公里，
而旅途中有若干个加油站。
试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。
6.试用动态规划算法实现下列问题：设
A
和
B
是两个字符串。我们要用最尘轿少的字符操作，将字符串
A
转换为字符串
B，这里所说的字符操作包括：
①删除一个字符。
②插入一个字符。
③将一个字符改为另一个字符。
请写出该算法。
7.对于下图使用
Dijkstra
算法求由顶点
a
到顶点
h
的最短路径。
8.试写出用分治法对数组
A[n]实现快速排序的算法。
9.有
n
个活动争用一个活动室。
已知活动
i
占用的时间区域为[s
i
，
f
i
]，
活动
i,j
相容的条件是：
sj≥f
i
，问题的解表示为(x
i
|
x
i
=1，2…，n,)，x
i
表示顺序为
i
的活动编号活动，求一个相容的活动子
集，且安排的活动数目最多。
10.设
x
1
、
x
2
、
x
3
是一个三角形的三条边，而且
x
1
+x
2
+x
3
=14。请问有多少种不同的三角形？给出解答过
程。
11.设数组
A
有
n
个元素，需要找出其中的最大最小值。
①请给出一个解决方法，并分析其复杂性。
②把
n
个元素等分为两组
A1
和
A2，分别求这两组的最大值和最小值，然后分别将这两组的最大值
和最小值相比较，求出全部元素的最大值和最小值。如果
A1
和
A2
中的元素多于两个，则再用上述
方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想？请给出该方法的
算法描述，并分析其复杂性。
12.有
n
个程序和长度为
L
的磁带，
程序
i
的长度为
a
i
，
已知
L
a
n
i
i
≻
∑
=
1
，
求最优解(x
i
，
x
2
，
...，
x
i
，
…，
x
n
)，x
i
=0，1,
x
i
=1，表示程序
i
存入磁带，x
i
=0，表示程序
i
不存入磁带，满足
L
a
x
n
i
i
i
≤
∑
=
1
，
且存放的程序数目最多。
13.试用分治法实现有重复元素的排列问题：设
)
,...,
,
{
2
1
n
r
r
r
R
=
是要进行排列的
n
个元素，其中元素
n
r
r
r
,...,
,
2
1
可能相同，试设计计算
R
的所有不同排列的算法。
14.试用动态规划算法实现
0-1
闭包问题，请写出该算法。
15.试用贪心算法求解下列问题：将正整数
n
分解为若干个互不相同的自然数之和，使这些自然数的乘
积最大，请写出该算法。
16.试写出用分治法对一个有序表实现二分搜索的算法。
17.试用动态规划算法实现最长公共子序列问题，请写出该算法。
18.假设有
7
个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量
M＝150，
使用回溯方法求解此背包问题，请写出状态空间搜索树。
物品
A
B
C
D
E
F
G
重量
35
30
60
50
40
10
25
价值
10
40
30
50
35
40
30
19.求解子集和问题：对于集合
S={1，2
，6，8}，求子集，要求该子集的元素之和
d=9。
①画出子集和问题的解空间树；
②该树运用回溯算法，写出依回溯算法遍历节点的顺序；
③如果
S
中有
n
个元素，指定
d，用伪代码描述求解子集和问题的回溯算法。
20.求解填字游戏问题：在
3×3
个方格的方阵中要填入数字
1
到
N（N≥10）内的某
9
个数字，每个方
格填一个整数，似的所有相邻两个缺兄纳方格内的两个整数之和为质数。试采用回溯法写出满足这个要求
的一种数字填法的算法和满足这个要求的全部数字填法的算法。
21.试用动态规划算法实现最大子矩阵和问题：
求
n
m
×
矩阵
A
的一个子矩阵，
使其各元素之和为最大。
22.试用回溯法解决下列整数变换问题：关于整数
i
的变换
f
和
g
定义如下：
⎣
⎦
2
/
)
(
;
3
)
(
i
i
g
i
i
f
=
=
。
对于给定的两个整数
n
和
m
，要求用最少的变换
f
和
g
变换次数将
n
变为
m
。
23.关于
15
谜问题。在一个
4×4
的方格的棋盘上，将数字
1
到
15
代表的
15
个棋子以任意的顺序置入
各方格中，空出一格。要求通过有限次的移动，把一个给定的初始状态变成目标状态。移动的规则
是：每次只能把空格周围的四格数字（棋子）中的任意一个移入空格，从而形成一个新的状态。为
了有效的移动，设计了估值函数
C
1
(x)，表示在结点
x
的状态下，没有到达目标状态下的正确位置
的棋子的个数。