这题不难啊。。。标记一下就行了。表示啥想法也没有。
#include <cstring>
#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
#define INF 100000000
int dp[];
int flag[];
int p[];
int o[];
int que[];
int pre[];
int main()
{
int i,j,n,m;
scanf("%d%d",&m,&n);
for(i = ; i <= n; i ++)
scanf("%d",&p[i]);
for(i = ; i <= m; i ++)
dp[i] = INF;
flag[] = ;
for(i = ; i <= n; i ++)
{
for(j = m; j >= p[i]; j --)
{
if(dp[j] > dp[j-p[i]] + p[i])
{
dp[j] = dp[j-p[i]] + p[i];
pre[j] = i;
}
if(dp[j] == dp[j-p[i]] + p[i])
{
flag[j] += flag[j-p[i]];
}
}
}
if(dp[m] != m)
printf("0\n");
else if(flag[m] > )
printf("-1\n");
else
{
while(m)
{
o[pre[m]] = ;
m -= p[pre[m]];
}
int z = ;
for(i = ; i <= n; i ++)
{
if(!o[i])
{
if(z)
{
printf("%d",i);
z = ;
}
else
printf(" %d",i);
}
}
}
return ;
}