POJ1742 coins 动态规划之多重部分和问题

时间:2023-03-09 06:14:18
POJ1742 coins    动态规划之多重部分和问题

原题链接:http://poj.org/problem?id=1742

题目大意:tony现在有n种硬币,第i种硬币的面值为A[i],数量为C[i]。现在tony要使用这些硬币去买一块价格不超过m的表。他希望买的时候不用找零,问有多少种价格能满足这一点。

这个问题实际上是一个多重部分和的问题:假设有n种物品,每种物品的价值为v[i],数量为c[i],随意选取这些物品,能否使它们的价值之和恰好为m。使用动态规划的思想来求解这类问题:

定义dp数组,dp[i][j]的值代表前i种物品随意选取,价值之和为j时第i种物品最多能剩下多少个,当前i种物品无法使价值之和刚好为j时,其值为-1。那么,很明显,递推关系存在四种情况:

①:如果dp[i - 1][j] >= 0,也就是说前i - 1种物品已经可以组合得到j,此时第i种物品可以一件也不取,即dp[i][j] = c[i];

②:如果不满足情况①,那么我们要通过在第i种物品中选取来使价值之和为j,但如果j的值小于v[i]的话,哪怕只选取一个也会超过j,所以此时无法实现要求,dp[i][j] = -1;

③:如果不满足情况①且j又不小于v[i]时,也许我们可以通过选取a个第i种物品来使价值之和恰好为j(1 <= a)。如果可以的话,那么选取a - 1个一定可以使价值之和为j - v[i],所以dp[i][j]可以由dp[i][j - v[i]]推出。如果dp[i][j - v[i]]等于-1(无法实现)或者等于0(第i种物品已用完),dp[i][j]都等于-1;

④:在情况③中,如果在第i种中拿a个能使价值之和为j - v[i],且第i种物品还有剩余,那再拿一个就可以使价值之和为j了,即dp[i][j] = dp[i][j - v[i]] - 1。

有了这些递推关系,我们就可以用如下的代码来求解多重部分和问题:

int n;//物品种数
int m;//目标和
int v[n];//每种物品的价值
int c[n];//每种物品的数量
memset(dp, -, sizeof(dp));
dp[] = ;//初始化
for(int i = ;i < n;i++)
{
for(int j = ;j <= m;j++)
{
if(dp[j] >= )//情况①
{
dp[j] = c[i];
//这里滚动使用了一个一维数组,dp[j]在更新前代表的是上一轮的值(即二维的dp[i - 1][j])或初始值
}
else if(j < v[i] || dp[j - v[i]] <= )//情况②、③
{
dp[j] = -;
}
else//情况④
{
dp[j] = dp[j - v[i]] - ;
}
}
}

这道poj1742只是在上面这个问题的基础上略加变形,我们只需要遍历dp数组求出1-m中有多少中价格可以被组合出来即可得到答案。

不过这种解法在POJ上耗时1800ms左右,虽然可以ac,但可能无法应付更大的数据规模或者更高的效率要求,我们还可以借助二进制优化或者各种数据结构来进一步提高效率。