|Tyvj|ダイナミックプランニング|P 1015道路乗車


http://tyvj.cn/p/1015
旅客の総行程数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; }