C :

#include<stdio.h>
int f[100010], c, n, m;
int min(int a, int b) {return a < b ? a : b; }
int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        if(n==0 && m==0)
            break;
        for (int j = 1; j < m + 1; ++j)
            f[j] = 0x7ffffffe;
        for (int i = 1; i < n + 1; ++i)
        {
            scanf("%d", &c);
            for (int j = c; j < m + 1; ++j)
                f[j] = min(f[j], f[j - c] + 1);
        }

        for (int j = m; j > 0; --j)
            if (f[j] < 0x7ffffffe){
                printf("%d\n", f[j]);
                break;
            }
    }

    return 0;
}

C++ :

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std ;

const int INF = ( 1 << 31 ) - 1 ;

int ans[100000+10] ;

int main() {

    int n , t ;
    while( ~scanf("%d%d" , &n , &t ) && n ) {
        for( int i = 1 ; i <= t ; i ++ ) ans[i] = INF ; ans[0] = 0 ;
        for( int i = 0 ; i < n ; i ++ ) {
            int d ; scanf("%d" , &d ) ;
            for( int j = d ; j <= t ; j ++ ) ans[j] = min( ans[j] , ans[j-d] == INF ? INF : ans[j-d] + 1 ) ;
        }
        while( ans[t] == INF ) t -- ;
        printf("%d\n" , ans[t] ) ;
    }

    return 0 ;
}

Java :

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), t = sc.nextInt();
        while (n!=0 && t!=0) {
            int[] type = new int[n];
            for (int i = 0; i < n; i++) type[i] = sc.nextInt();
            long ans = lessCoin(type, t);
            System.out.println(ans);
            n = sc.nextInt();t = sc.nextInt();
        }
    }

    static long lessCoin(int[] type, int total) {
        long[] dp = new long[(int) (1e5+7)];
        for (int coin : type) dp[coin] = 1;
        for (int i = 1; i <= total; i++) {
            long min = Integer.MAX_VALUE;
            for (int coin : type) if (i - coin >= 0 && dp[i-coin] != Integer.MAX_VALUE) min = Math.min(min, 1 + dp[i - coin]);
            dp[i] = min;
        }
        if (dp[total] != Integer.MAX_VALUE) return dp[total];
        for (int j = total - 1; j > 0 ; j--) if (dp[j] != Integer.MAX_VALUE) return dp[j];
        return -1;
    }
}