Lintcode92 Backpack solution 题解

Nicole 2017-08-11
【题目描述】


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)

【参考答案】

www.jiuzhang.com/solutions/backpack/

查看更多主题的豆瓣日记和相册

Nicole
作者Nicole
12日记 0相册

全部回应 0 条

添加回应

Nicole的热门日记

值得一读

    豆瓣
    我们的精神角落
    免费下载 iOS / Android 版客户端