#include <iostream>
#include <vector>
using namespace std;
#define SIZE 20020
#define INF 1000000
int dp[SIZE],coin[SIZE];
int generate(int n,int m);
int main()
{
int test,i,n,m;
scanf("%d",&test);
while(test--)
{
scanf("%d",&n); //target point
scanf("%d",&m);
for(i=0;i<m;i++)
scanf("%d",&coin[i]);
generate(n,m);
}
}
int generate(int n,int m)
{
int i,j,high;
for(i=0;i<SIZE;i++)
dp[i]=INF;
dp[0]=0;
high=0;
for(i=0;i<m;i++)
{
for(j=n;j>=0;j--)
{
dp[j+coin[i]]=min(dp[j]+1,dp[j+coin[i]]);
}
}
if(dp[n]!=INF)
printf("Minimum Coin:%d\n",dp[n]);
else printf("Impossible\n");
}
No comments:
Post a Comment