tyvj p1015公路乘车-动态规划dp-完全背包

83 阅读 0 评论 55 点赞

我是靠谱客的博主缓慢未来，最近开发中收集的这篇文章主要介绍tyvj p1015公路乘车-动态规划dp-完全背包，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目地址：http://www.tyvj.cn/p/1015

P1015 公路乘车

描述

一个特别的单行街道在每公里处有一个汽车站。顾客根据他们乘坐汽车的公里使来付费。例如样例的第一行就是一个费用的单子。

没有一辆车子行驶超过10公里，一个顾客打算行驶n公里（1<=n<=100），它可以通过无限次的换车来完成旅程。最后要求费用最少。

输入格式

第一行十个整数分别表示行走1到10公里的费用（<=500）。注意这些数并无实际的经济意义，即行驶10公里费用可能比行驶一公里少。
第二行一个整数n表示，旅客的总路程数。

输出格式

仅一个整数表示最少费用。

输入

12 21 31 40 49 58 69 79 90 101
15

输出

147

解题思路

分别乘车行驶1-10公里表示10个物品，行驶的公里数表示物品的消耗，花费的钱表示价值，一共走的公里数n是背包容量，因为可以无限次换成，所以相当于一个物品可以拿好多次，完全背包问题。这求的是最小花费，所以把初始值设为无限大，f[0]=0;

代码

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int f[110];//行驶i公里花的最小费用
int v[12];//行驶i公里花的钱
const int INF =0x3f3f3f3f;
int main()
{
int i,j;
int n;
for(i=1;i<=10;++i)
scanf("%d",&v[i]);
scanf("%d",&n);
memset(f,INF,sizeof(f));
f[0]=0;//行驶零公里费用是零
for(i=1;i<=10;++i)
{
//for(j=1;j<=n&&j>=i;++j)这种写法是错误的，如果j<i，就跳出循环了，而我想要的是使j++；
//for(j=i;j<=n;++j)
for(j=1;j<=n;++j)
{
if(j>=i)
f[j]=min(f[j],f[j-i]+v[i]);
}
}
printf("%d",f[n]);
return 0;
}