背包问题

背包问题

【问题描述】
简单的背包问题。设有一个背包,可以放入的重量为s。现有n件物品,重量分别为t1 , t2 , t3 … ti … tn ,ti (1≤ i≤n),均为正整数。从n件物品中挑选若干件,使得放入背包的重量之和正好为s。若找不到相关解,则输出“not found”
【输入格式】
第一行是物品总件数和背包的载重量,第二行为各物品的重量
【输出格式】
各所选物品的序号和重量。
【输入样例】
5 10
1 2 3 4 5
【输出样例】
number:1 weight:1
number:4 weight:4
number:5 weight:5