#607. wjr 的背包问题
wjr 的背包问题
说明
wjr 最近在学习动态规划的经典问题————背包问题
题目是这样的:总共有 n 种物品,每种物品的数量有无限个,每种物品有一个体积 a_i
现在 wjr 已经选出了 m 个物品,并且程序输出了一个结果表示已经选的物品体积总和
但是他不知道自己的程序是否正确
于是他想知道, m 种物品有多少种可能的体积之和?
他希望你可以告诉他所有的可能性,并且按照升序从小到大输出
输入格式
第一行两个整数,分别表示 n,m接下来一行 n 个数,第 i 个数表示 a_i 表示每种物品的体积
对于 20% 的数据,n,m <= 30
对于 50% 的数据,n,m <= 100
对于 100% 的数据,n,m,a_i <= 500
输出格式
按照升序顺序输出所有可能的体积之和样例
3 3
2 3 5
6 7 8 9 10 11 12 13 15