- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
您和您的 friend 正开车前往蒂华纳度春假。您正在为旅行省钱,因此您希望尽量减少途中的汽油费用。为了最大限度地减少您的天然气成本,您和您的 friend 整理了以下信息。首先,您的汽车可以通过一箱油可靠地行驶 m 英里(但不能再远)。您的一位 friend 从网上挖掘了加油站数据,并绘制了您路线上的每个加油站以及该加油站的汽油价格。具体来说,他们创建了一个从最近到最远的 n+1 个加油站价格列表以及两个相邻加油站之间的 n 距离列表。塔科马是 0 号加油站,蒂华纳是 n 号加油站。为了方便起见,他们将汽油成本转换为汽车行驶每英里的价格。此外,还计算了两个相邻加油站之间的英里距离。您将在加满油的情况下开始您的旅程,当您到达蒂华纳时,您将为返程加满油。您需要确定在哪些加油站 parking ,以最大限度地降低旅途中的汽油成本。
示例输入:
价格(每英里美分)[12,14,21,14,17,22,11,16,17,12,30,25,27,24,22,15,24,23,15,21]
距离(英里)[31,42,31,33,12,34,55,25,34,64,24,13,52,33,23,64,43,25,15]
您的汽车加一箱油可以行驶 170 英里。
我的输出:
此次旅行的最低费用为:117.35 美元
加油站停靠:[1, 6, 9, 13, 17, 19]
我已经解决了这个问题,但我不确定我是否做对了。如果错误的话,有人可以给我一些建议或指出正确的方向吗?预先感谢您。
public class GasStation {
/** An array of gas prices.*/
private int[] myPrice;
/** An array of distance between two adjacent gas station.*/
private int[] myDistance;
/** Car's tank capacity.*/
private int myCapacity;
/** List of gas stations to stop at to minimize the cost.*/
private List<Integer> myGasStations;
/**
* A constructor that takes in a price list, distance list, and the car's tank capacity.
* @param thePrice - price list
* @param theDistance - distance list
* @param theCapacity - the car's capacity
*/
public GasStation(final int[] thePrice, final int[] theDistance,
final int theCapacity) {
myPrice = thePrice;
myDistance = theDistance;
myCapacity = theCapacity;
myGasStations = new ArrayList<>();
}
/**
* Calculate for the minimum cost for your trip.
* @return minimum cost
*/
public int calculateMinCost() {
int lenP = myPrice.length;
int lenD = myDistance.length;
if (lenP == 0 || lenD == 0 || myCapacity == 0) return 0;
// gas station -> another gas station (moves)
Map<Integer, Integer> gasD = new HashMap<>();
int[] D = new int[lenD + 1];
D[0] = 0;
// calculate the total distance
for (int i = 0; i < lenD; i++) {
D[i + 1] = D[i] + myDistance[i];
}
int len = D.length;
for (int i = 1; i < len - 1; i++) {
int j = len - 1;
while (D[j] - D[i] >= myCapacity) {
j--;
}
gasD.put(i, j - i);
}
int min = Integer.MAX_VALUE;
for (int i = 1; i < len; i++) {
int temp = 0;
int cur = i;
List<Integer> tempList = new ArrayList<>();
if (D[i] <= myCapacity) {
temp = D[cur] * myPrice[cur];
tempList.add(cur);
int next = gasD.get(cur) + cur;
while (next < len) {
temp += (D[next] - D[cur]) * myPrice[next];
cur = next;
tempList.add(cur);
if (gasD.containsKey(cur)) next = gasD.get(cur) + cur;
else break;
}
if (temp < min) {
min = temp;
myGasStations = tempList;
}
}
}
return min;
}
/**
* Get gas stations to stop at.
* @return a list of gas stations to stop at
*/
public List<Integer> getGasStations() {
return myGasStations;
}
}
最佳答案
让最小的补充成本为 station i
表示为cost[i]
给定问题陈述,如何表达此成本?
我们知道,每次下一次补充都必须在 170 miles
内完成。远离最后一次补充,
因此最小成本可以表示为:
cost[i] = MIN { cost[j] + price[i] * distance_from_i_to_j } for every j such that distance(i,j) <= 170 mi
带有基本案例cost[0] = 0
如果我们不考虑 station 0
的全 jar 成本,否则基本情况为 cost[0]= 170 * price[0]
我假设我们不考虑 station 0
处的全 jar 成本,并且在最后一点不需要补充,即 station 19
通过查看上面定义的递归关系,我们可以很容易地注意到同一子问题被多次调用,这意味着我们可以利用动态规划解决方案来避免可能的指数运行时间。
另请注意,因为我们不需要在 station 19
处重新填充,我们应该计算一下加油站的加油费用1
通过18
仅,即 cost[1], cost[2], .., cost[18]
。这样做之后,问题的答案将是 MIN { cost[14], cost[15], cost[16], cost[17], cost[18] }
因为唯一的车站位于距 station 19
170 英里以内的地方是站14,15,16,17,18
这样我们就可以到达车站19
在这 5 个加油站之一进行加油。
当我们定义了上述与基本情况的递归关系后,我们可以通过以下方式将其转换为循环:
int price[] = {12,14,21,14,17,22,11,16,17,12,30,25,27,24,22,15,24,23,15,21}; //total 20 stations
int distance[] = {31,42,31,33,12,34,55,25,34,64,24,13,52,33,23,64,43,25,15}; //total 19 distances
int N=19;
int[] cost = new int[N];
int[] parent = new int[N]; //for backtracking
cost[0] = 0; //base case (assume that we don't need to fill gas on station 0)
int i,j,dist;
int maxroad = 170;
for(i=0; i<N; i++) //initialize backtracking array
parent[i] = -1;
for(i=1; i<=N-1; i++) //for every station from 1 to 18
{
int priceval = price[i]; //get price of station i
int min = Integer.MAX_VALUE;
dist = 0;
for(j=i-1; j>=0; j--) //for every station j within 170 away from station i
{
dist += distance[j]; //distance[j] is distance from station j to station j+1
if(dist>maxroad)
break;
if((cost[j] + priceval*dist)<min) //pick MIN value defined in recurrence relation
{
min = cost[j] + priceval*dist;
parent[i] = j;
}
}
cost[i] = min;
}
//after all costs from cost[1] up to cost[18] are found, we pick
//minimum cost among the stations within 170 miles away from station 19
//and show the stations we stopped at by backtracking from end to start
int startback=N-1;
int answer=Integer.MAX_VALUE;
i=N-1;
dist=distance[i];
while(dist<=maxroad && i>=0)
{
if(cost[i]<answer)
{
answer = cost[i];
startback=i;
}
i--;
dist += distance[i];
}
System.out.println("minimal cost=" + answer + "\nbacktrack:");
i=startback;
while(i>-1) //backtrack
{
System.out.println(i + " ");
i = parent[i];
}
关于java - 加油站动态规划,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53357989/
在 JavaScript 中,我们可以动态创建 元素并附加到 部分,以便为大量元素应用 CSS 规则。 这种方法的优点或缺点是什么? 如果它确实提供了与元素上的 javascript 迭代相比的性
我有这个代码 import "./HTTPMethod.dart"; import '../../DataModel/DataModel.dart'; mixin RouterMixin { HT
哪些 OLAP 工具支持动态、动态地创建维度或层次结构? 例如,层次结构将成员定义为:“前 5 名”、“前 6-10 名”、“其他”... 计算成员是通常的答案,我正在寻找不同的东西。计算器的问题。成
我正在 CakePHP 中创建一个“表单编辑器”。 该界面允许用户选择要应用于字段的验证,例如数字、电子邮件等 因此,我需要根据用户输入为模型动态创建验证。为此,我可以使用验证对象:https://b
这是一个场景: 我有一个Web服务,我们将其称为部署在tomcat(轴)上的StockQuoteService。通过此 Web 服务公开了 getStockQuote() 方法。 现在,我想构建一个
我正在尝试从服务器获取 JSON 响应并将其输出到控制台。 Future login() async { var response = await http.get( Uri.
我从另一个问题中得到了这段代码(感谢 chunhunghan)。我需要创建一个登录屏幕,并尝试根据服务器发回给我的响应来验证用户凭据,但是每次我尝试运行代码时,它都会给我“未处理的异常:Interna
当我在“Dart”主程序中运行它时,一切正常,并且我得到了一个与会者列表。但是,当我在我的 Flutter 应用程序中调用它时,出现错误: flutter:“List”类型不是“List>”类型的子类
本文实例为大家分享了js实现验证码动态干扰的具体代码,供大家参考,具体内容如下 效果一 效果二 代码一 ?
目前我正在为我的网站使用 No-Ip,我想使用 cloudflare 来抵御 ddos 和机器人程序。我注意到您需要一个用于 cloudflare 的域。我还搜索了网络,发现了一个叫做 cloud
有没有办法在 Excel VBA 中构建动态 if 语句?基本上我正在尝试创建一个参数化计算,用户将能够输入不同的变量,即 变量 1 “变量 2” “变量 3” 在这种情况下 变量 1 是单元格引用
大家好, 请查看上面的图片,我有两张 table 。在下面代码的第一个表中,我得到了这种格式。 但我想像 Table2 那样格式化,每个合并单元格中的行数是动态的,而且不一样。 有没有办法像table
如何根据我添加的 View 修改标题部分的高度?heightForHeaderInSection在 viewForHeaderInSection 之前被调用我不知道 View 大小,直到我创建它。 最
是否存在在运行时生成 AST/解析树的解析器?有点像一个库,它会接受一串 EBNF 语法或类似的东西并吐出数据结构? 我知道 antlr、jlex 和他们的同类。他们生成可以做到这一点的源代码。 (喜
我在持有汽车制造商的表格上有一个 MultipleChoiceField。我想将我的汽车数据库过滤到已检查的品牌,但这会导致问题。如何动态获取所有 Q(make=...) 语句? 我如何开始:['va
$end = preg_replace($pattern, $replacement, $str); 如何使替换字符串 $replacement 随 $str 中的每次匹配而变化?例如,我想用关联的图
我正在编写一个 VBA 程序,用于过滤表中的值。我试图使其成为一个适用于您提供的所有表格的通用程序。在我的程序中,我必须设置它正在过滤的表的范围:Set rng = dataSheet.Range("
我正在循环一个元素数组,并且我想使用给定的模板递归地显示该元素 然后在该模板内使用带有切换功能的按钮来显示/隐藏给定元素的Child的更深级别模板(Child也是一个元素) 这是我的模板
从客户端(html)发送表单,服务器端通过选择选项之一决定运行哪个函数。 const decideWho = (form) => { const choice = form.choice; c
我有一个具有以下属性的按钮: circle_normal.xml(在 res/drawable 中) circle.xml(在 res/drawable 中)
我是一名优秀的程序员,十分优秀!