「POJ 1742」Coins

题目链接:POJ1742

Description

给你$n$个物品,每个物品有价值$a_i$,数量$v_i$,让你统计在范围$[1,m]$内,价值和可以组成多少不同的数。

Data Range

$n\leq 100, m\leq 10^5$

Solution

关于能否到达的DP,有以下几种解法

Solution 1

$f[i]$表示能否组成$i$这个数,考虑从$1->m$顺推,可以比较显然得到的转移方程就是:

$f[j]|=f[j-p[i]]$

考虑到是多重背包,所以需要注意递推的顺序,但是数据范围较大,复杂度为$O(n^2m)$是无法过去的,考虑记录最小的更新的步数。

复杂度为$O(nm)$。

Code

Solution 2

考虑优化多重背包的个数循环。都知道,形如$1,2,4,8$的数列可以将$2^{n+1}-1$内的所有数都表示出来,所以考虑多重背包的二进制优化,将每一个物品的个数拆分成二进制,然后做$01$背包即可。

最后修改:2019 年 07 月 29 日 03 : 32 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论