题目描述

奶牛手上有 N 枚硬币，第 i 枚硬币的面值是 d[i] 元。无人售货机有 1000 件礼物，编号从 1 至 1000 ，第件礼物需要 i 元，售货机不设找赎。奶牛想知道：对于第 i 件礼物，至少需要有多少枚凑币才能凑出 i 元？

输入格式

第一行，一个整数 N 。1<=N<= 40。

第二行，N 个整数，第 i 个整数是 d[i] 。1 <= d[i] <= 100。

输出格式

一行，共 1000 个整数，第 i 个整数表示凑出 i 元至少需要的硬币数，如果无法凑出 i 元则输出 -1 。

样例

5
3 2 3 7 2

-1 1 1 2 2 2 1 3 2 2 3 3 3 4 4 -1 5 -1 -1 -1 -1 -1 -1 -1......-1

完善程序

#include<bits/stdc++.h>
using namespace std;
int n;
int a[105];
long long dp[1005]; 
int main()
{
	cin >> n;
	for (int i=0;i<n;i++)
		cin >> a[i];
	
	memset(dp, -1, sizeof(dp));   //初始化数组值为-1
	
	dp[0] = __填空(1)__ ;
	for (int i = 0; i < n; i++)  
		for (int j = 1000; j >= a[i]; j--) 
			if (dp[j-a[i]] >= 0)      //子问题存在
			{
				if (dp[j] == -1) dp[j] = __填空(2)__ ;
				else  dp[j] = min(dp[j], __填空(3)__) ;
			}
	
	for(int i=1;i<=1000;i++) 
		cout<<dp[i]<<' ';
	
	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}