1286最適なストレージ

説明
長さLのテープにn個のプログラム{1,2,...,n}を格納する.プログラムiを格納するには、テープの長さをLiとし、1<=i<=nとする必要がある.テープにできるだけ多くのプログラムを格納できるように、ストレージスキームを設計していただきたいと思います.最も多くのプログラムを保存することを前提として、テープの利用率を最大化する必要があります.
入力
第1の動作は、Tグループのテストデータがあることを示す整数Tである.
各試験データのセットについて、第1行は正の整数L(106を超えない)であり、テープの長さを表す.2行目は正の整数n(100を超えない)であり、n個のプログラムがあることを示す.3行目はn個の正の整数(各数の数値は100を超えない)であり、i番目の数値Liは、記憶に必要なテープ長がLiであり、各数がスペースで区切られていることを示す.
しゅつりょく
各テストデータのセットについて、最初の行は正の整数であり、テープに格納できるプログラムの最大数を示します.2行目は、テープに格納されているプログラムの合計テープ長を示す正の整数です.
サンプル入力

1

60

10

2 3 8 10 12 13 16 21 23 80

サンプル出力

6

60

 
リュックサックの問題に似たダイナミックな計画

#include <stdio.h>
#include <string.h>
main()
{
	int number,te;
	long int l;
	int a[101];
	int n;
	int i;
	int j;
	int cnt[10001];
	int sum;
	scanf("%d",&number);

	for(te=1;te<=number;te++)
	{  
		memset(cnt,0,sizeof(cnt));

		scanf("%ld",&l);
		scanf("%d",&n);
		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);
  
		sum=0; 
		for(i=1;i<=n;i++)
			sum+=a[i];

		if(sum<l)
			l=sum;
		if(sum==l)
		{
			printf("%d
",n);
			printf("%d",sum);
			goto ABC;
		}
        for(i=1;i<=n;i++)
			for(j=l;j>=0;j--)
			{
				if(cnt[j-a[i]]+1>cnt[j]&&j-a[i]>=0)
					cnt[j]=cnt[j-a[i]]+1;
				else
					cnt[j]=cnt[j];
			}


			for(j=l;j>=0;j--)
				if(cnt[j]!=0)
					break;



				  printf("%d
",cnt[j] );

				printf("%d",j);

		
			






ABC: printf("
");
	}
}