1244.Gentlemen

http://acm.timus.ru/problem.aspx?space=1&num=1244
リュックサックの問題  理解は難しくない
答えが複数あれば出力します.
一つの答えは結果を出力します.   出力0
sum[n]でnまでいくつかのパスがありますか?
状態遷移方程式は 
if(sum[j-a[i])//a[i]はi番目のデータのサイズを表します.
{        sum[j]=max(sum[j]+1,sum[j-a[i])
)
コードとそのコメント:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>



#define LL long long



using namespace std;



const int N=100003;

int sum[N];//  N      

int f[N];//              

int a[103];//     

bool select[103];//    

void Fselect(int x)//         

{

    while(x)

    {

        select[f[x]]=true;

        x=x-a[f[x]];

    }

}

int main()

{

    //freopen("data.txt","r",stdin);

    int K,n;

    while(scanf("%d %d",&K,&n)!=EOF)

    {

        memset(sum,0,sizeof(sum));

        sum[0]=1;

        memset(select,false,sizeof(select));

        int m=0;

        for(int i=1;i<=n;++i)

        {

            scanf("%d",&a[i]);

            if(sum[K]>1)//             

            continue;

            m=min(m+a[i],K);//  

            for(int j=m;j>=a[i];--j)

            {

                if(sum[j]==0)//                     

                {

                    f[j]=i;

                }

                if(sum[j-a[i]])//        

                {

                   sum[j]=max(sum[j]+1,sum[j-a[i]]);

                }

            }

            if(sum[K]==1)

            Fselect(K);

        }

        if(sum[K]==0)

        {printf("0
");continue;}

        if(sum[K]>1)

        {printf("-1
");continue;}

        for(int i=1;i<=n;++i)

        {

            if(!select[i])

            printf("%d ",i);

        }

        printf("
");

    }

    return 0;

}