题目内容

小塔正在整理他的玩具，他遇到了一道有趣的装箱问题:他有一个容量为$N$的箱子，并且有$n$个大小为$a[i]$的玩具。

除了这$n$个玩具外，还有$c$个大小均为$1$的填充物，它们是小塔参加各种活动的纪念品，正好可以拿来填充缝隙。

他的任务是确定是否可以选其中一些玩具(填充物也包含在内)放入箱子中，恰好装满箱子，而不留下任何空隙。

思路:背包问题

本质就是给n个物品以及c个大小为1的物品，询问是否能组成目标N.

这是一个典型的01背包问题，给定n个物品和c个大小为1的物品，判断能否组合出目标N。使用动态规划的方式解决，dp[i]表示是否能组成大小为i的目标。由于size = 1 的物品比较多，而且他们可以连续组成[0,c]的大小空间。所以我们只对这n个物品进行背包，然后最后判断N - c 到 N之间有dp[x] = True 的就行。

代码

java