Module: Le problème du sac à dos


Problem

2 /6


Sac à dos 0-1 : éléments minimum

Problem

Étant donné N éléments de masse m1, …, mN. Ils remplissent un sac à dos qui peut supporter un poids ne dépassant pas M. Comment prendre du poids en M exactement en utilisant le moins d'articles possible ?
 
Saisie :
- la première ligne contient un nombre naturel N n'excédant pas 100 et un nombre naturel M n'excédant pas 10000 ;
- la deuxième ligne contient N nombres naturels mi ne dépassant pas 100.
 
Sortie : Imprimez le plus petit nombre d'articles dont vous avez besoin, ou 0 si vous ne pouvez pas atteindre le poids donné.
 

 

Exemples
1 5968
18
# Entrée Sortie
1 0

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!