【题目描述】
Givennitems with size Ai, an integermdenotes the size of a backpack. How full you can fill this backpack?
在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]
【注】：你不可以将物品进行切割。
【题目链接】
www.lintcode.com/en/problem/backpack/
【题目解析】
本题是典型的01背包问题，每种类型的物品最多只能选择一件。
1.状态: result[i][S] 表示前i个物品，取出一些物品能否组成体积和为S的背包
2.状态转移方程: f[i][S]=f[i−1][S−A[i]] or f[i−1][S] (A[i]为第i个物品的大小)
1.欲从前i个物品中取出一些组成体积和为S的背包，可从两个状态转换得到。
i.f[i−1][S−A[i]]:放入第i个物品，前i−1 个物品能否取出一些体积和为 S−A[i] 的背包。
ii.f[i−1][S]:不放入第i个物品，前i−1 个物品能否取出一些组成体积和为S的背包。
3.状态初始化: f[1⋯n][0]=true; f[0][1⋯m]=false. 前1~n个物品组成体积和为0的背包始终为真，其他情况为假。
4.返回结果: 寻找使 f[n][S] 值为true的最大S (1≤S≤m)
【参考答案】
