|Tyvj|ダイナミックプランニング|P 1015道路乗車
693 ワード
http://tyvj.cn/p/1015
旅客の総行程数nをリュックサック総量とし、10 km毎kmの費用を物品の価値とし、10 km毎kmのkm数は物品の重量であり、最小価値を求める.
例えば5 km料金が49なら価値は49、重量は5.
そして完全バックパックで作ります.
旅客の総行程数nをリュックサック総量とし、10 km毎kmの費用を物品の価値とし、10 km毎kmのkm数は物品の重量であり、最小価値を求める.
例えば5 km料金が49なら価値は49、重量は5.
そして完全バックパックで作ります.
#include
#include
#include
using namespace std;
int main ()
{
const int maxn = 100 + 5;
int a[15];
for (int i=1;i<=10;i++) scanf("%d", &a[i]);
int n;
scanf("%d", &n);
int f[maxn];
for (int i=1;i<=n;i++) f[i] = 30000;
f[0] = 0;
for (int i=1;i<=10;i++)
{
for (int j=0;j<=n;j++)
{
if (j>=i) f[j] = min(f[j], f[j-i]+a[i]);
}
}
printf("%d
", f[n]);
return 0;
}