题意 : 给出一幅不完全的纸牌.算出哪些牌丢失了.
思路 : 算是背包一个吧。if f[j]>0 f[j+a[i]] += f[j];然后在记录一下路径。
//
#include <stdio.h>
#include <string.h>
#include <iostream> using namespace std ; int a[] ,b[];
int dp[] ; int main()
{
int w ;
while(~scanf("%d",&w))
{
int N ;
scanf("%d",&N) ;
for(int i = ; i <= N ; i++)
scanf("%d",&a[i]) ;
memset(dp,,sizeof(dp)) ;
memset(b,,sizeof(b)) ;
dp[] = ;
for(int i = ; i <= N ; i++)
{
for(int j = w ; j >= ; j--)
{
if(dp[j] > && (j+a[i] <= w))
{
dp[j+a[i]] += dp[j] ;
if(b[j+a[i]] <= )
b[j+a[i]] = i;
}
}
}
if(dp[w] == )
printf("0\n") ;
else if(dp[w] > )
printf("-1\n") ;
else
{
int c[] ;
memset(c,,sizeof(c)) ;
for(int i = N ; i >= ; i--)
{
if(b[w] == i)
{
c[i] = true ;
w -= a[i] ;
}
}
for(int i = ; i <= N; i++)
if(c[i] == )
printf("%d ",i) ;
printf("\n") ;
}
}
return ;
}