跳格子 完全背包

sdut  2594

毛线除了泡妹子以外最喜欢的就是玩些无聊的游戏了。他最近又迷上了一个非常无聊的游戏,那就是...跳格子。他在墙边画了许许多多的格子,每次从外面往墙的那边跳,使自己更加靠近墙。

为了增加下游戏的难度,毛线每次跳之前会规定下自己每次能跳几个格子,然后试着让自己在这个限制下最靠近墙。

 

输入

 输入包含多组数据,对于每组测试数据:

第一个给出格子的总数 N(1<=N<=1000000),然后是 M(M<=10),接下来 M 行每行一个数 K(K<=N),表示毛线可以一次跳 K 格。

 

输出

 输出毛线最远可以跳到的地方离墙还有多少个格子。

 

示例输入

11 3
5
7
8
100 5
81
71
61
51
21

示例输出

1
7

提示

 第一组数据,毛线可以跳两次 5 格,这样距墙只有一格

第二组数据,毛线可以先跳 51 格,再跳两次 21 个,这样距墙只有 7 格

#include<stdio.h>   
#include<string.h>   
int c[20],dp[1000010];   
int main ()   
{   
    int n,m;   
    while(~scanf("%d %d",&n,&m))   
    {   
        for(int i = 0; i < m; i++)   
            scanf("%d",&c[i]);   
        memset(dp,0,sizeof(dp));   
        dp[0] = 1;   
        for(int i = 0; i < m; i++)   
            for(int j = c[i]; j <= n; j++) //顺序排列  
                if(dp[j-c[i]])   
                    dp[j] = 1;   
        for(int i = n; i >= 0; i--)   
            if(dp[i])   
            {   
                printf("%d\n",n-i);   
                break;   
            }   
    }   
    return 0;   
}