2017年11月30日23:04:39，还有9天，稳住能赢。

耍了两天斗志倒还没了，快放弃算法了。说实话，不知道省赛的acm到底比什么，我想对于专科的题目应该不是很难把。最近看的算法题，就已经让我怀疑难度的问题，主要目前我能解的来的还好说，我解不出来的真的是智商着急。目前还是要把心沉下来，毕竟算法这东西学了没有坏处，毕竟以后人工智能时代。

Acm题：

描述

一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。
对于给定的n和k个加油站位置，计算最少加油次数。

输入

第一行有2 个正整数n和k，表示汽车加满油后可行驶n公里，且旅途中有k个加油站。接下来的1 行中，有k+1 个整数，表示第k个加油站与第k-1 个加油站之间的距离。第0 个加油站表示出发地，汽车已加满油。第k+1 个加油站表示目的地。

输出

输出最少加油次数。
如果无法到达目的地，则输出2个字符：“No”。（不带引号）

样例输入

7 7

1 2 3 4 5 1 6 6

样例输出

4

题解：

对于这道题需要先判断有没有加油站的距离超过了最大油量的行驶距离，如果有就输出No。

如果没有就用贪心的思想去实现，每次加满油都行驶最大的距离。
如：设车辆行驶s距离，当s>n的时候就是需要加油的时候。S前面的路程就清空，s就等于下一个加油站的距离。

代码如下：

完整java代码：

0-1背包问题：

这个背包问题比较老火，上面的题做完后看了一个上午，没理解，午饭吃完继续找资料看，一个下午，勉强懂了一点，然后晚上试着去写代码。最后成功了。

最后把我教会的是以下下内容：

请允许我从一则故事说起…………

话说Lucy带着她的亲友团去沙漠寻求宝藏，经过几天几夜的长途跋涉，终于在沙漠的那一边发现了一堆个大无比、闪闪发光的钻石，一共有n个。可惜的是他们身上只有一个能装钻石的背包，背包的容量为W。Lucy兴奋之余，在一堆钻石中挑出突出的钻石编号排列：0,1,2,3……，n-1。第i个宝石对应的体积和价值分别为w[i]和v[i]。排好后Lucy开始思考，和向他的亲友团求助：背包总共只能装下体积为W的东西，那我要装下哪些钻石才能使我们获得最大的利益呢？

“很简单，用动态规划呀，那样我们就能获得最大的利益了”Bill斩钉截铁的回答，他边说着边用木棍在沙漠上笔画着。

说时迟那时快，Bill将挑出的5个钻石编号钻石，假设背包的容量范围在[0,17]，问题示例物品的价值和重量如下表

现在Bill考考读者,通过可放和不可放表，是不是就能罗列出在背包容量值固定，放入哪个编号的钻石，使获得价值量最大呢？

“我知道，我知道，这个智商大于0的人都知道”，聪明伶俐的Lucy抢先回答。看看我是如何计算的吧。

讲解：当w=3时，我只能放v<=3的钻石,对应着钻石的价值和重量表，很容易发现价值量为4；w=4同理；当w=7时，把体积v=3的钻石放入背包（然后背包剩下4的容量，可以装下第二个钻石，那还等什么麻利的装进背包呀！）此时背包放入的是编号为1、2钻石，价值量c=9。我想智商等于0的也知道，当我放入编号3钻石时，价值量c=10比上一步装法所获得的价值更大，于是乎接下来你知道怎么做了!

通过详细的列表求最优价值量，Lucy惊喜的发现一个规律，迫不及待的想分享给大家计算公式

最后java实现代码：

P：是背包的容量

n：是物品的数量

w、v分别是对应物品的体积和价值

c是价值表。

背包问题看完了去看了叉乘，相交，凸点，最后因时间太晚，没看完。留着明日做完一道题后再看。