DP:Coins(POJ 1742)

时间:2023-03-09 09:20:28
DP:Coins(POJ 1742)

                  DP:Coins(POJ 1742)

                  用硬币换钱

  题目大意:就是有面值为A1,A2,A3....的硬币,各有C1,C2,C3...的数量,问在钱数为m的范围内,能换多少钱?(不找零)

  这题看名字就知道是完全背包,但是这题又有点不一样,因为这题的硬币数不是无限的,所以我们要用点特殊的思路

  因为这题要我们求的是可以整换的钱的面值数,我们只要保证位置合法就可以了,所以dp矩阵内我们可以以面值数的剩余量为dp量,对于j<面值的位置,我们全部设置为当前面值的硬币数量,当j>=面值时,我们考虑两个位置:1:当上一个位置的这个位置合法(也就i-1面值的剩余硬币数>=0),那我们把dp[i][j]位置设置成当前硬币面值的总数(这个是贪心的思想,我们总是想把钱换更大的面值),

  如果dp[i-1][j]非法,那我们就往dp[i][j-coins[i-1]]的位置考量,如果dp[i][j-coins[i-1]]位置还有硬币剩余,那这个位置就dp[i][j-coins[i-1]]-1就好了,因为我们可以拿多一个硬币换出这个面值。

  然后如果dp[i][j-coins[i-1]]非法,那dp[i][j]这个位置自然也就非法了。

  最后再回头看一下上面的思路,我们发现我们只要一个一维数组就行了,因为对于k<j的位置,我们总是先考虑了,而且dp[i-1][j]我们只使用一次

  最后这题排一次序速度会快一点,数量比较小,直接插入排序就好了,复杂度O(n*m)

  最后吐槽一下自己,这一题wa了好几次,因为我一直把上一个位置考虑错了,本来应该考察dp[i-1][j]的,

   结果变成dp[i-1][j-coins[i-1]]DP:Coins(POJ 1742)

  

 #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX(a,b) (a)>(b)?(a):(b) typedef struct coins_set
{
int coins_value;
int coins_sum;
}SET; SET coins[];
int dp[]; void Search(const int, const int); void Insertion_Sort(const int n)
{
int i, j, tmp_v, tmp_s;
for (i = ; i <= n; i++)
{
tmp_v = coins[i].coins_value;
tmp_s = coins[i].coins_sum;
for (j = i; j > && coins[j - ].coins_value > tmp_v; j--)
{
coins[j].coins_value = coins[j - ].coins_value;
coins[j].coins_sum = coins[j - ].coins_sum;
}
coins[j].coins_value = tmp_v;
coins[j].coins_sum = tmp_s;
}
} int main(void)
{
int n, m, i;
while (~scanf("%d%d", &n, &m))
{
if (n == && m == )
break;
//读取钱的总量
for (i = ; i <= n; i++)
scanf("%d", &coins[i].coins_value);
for (i = ; i <= n; i++)
scanf("%d", &coins[i].coins_sum);
Insertion_Sort(n);
Search(n, m);
}
return ;
} void Search(const int n, const int m)
{
int i, j, ans = ; memset(dp, -, sizeof(dp));
for (i = ; i <= coins[].coins_sum; i++)//处理基准状态
{
if (i*coins[].coins_value <= m)
dp[i*coins[].coins_value] = coins[].coins_sum - i;
else break;
}
dp[] = coins[].coins_value;
for (i = ; i <= n; i++)
{
dp[] = coins[i].coins_value;
for (j = ; j <= m; j++)
{
if (j - coins[i].coins_value < )
dp[j] = dp[j] == - ? - : coins[i].coins_sum;
else
{
if (dp[j] != -)
dp[j] = coins[i].coins_sum;
else if (dp[j - coins[i].coins_value] > -)
dp[j] = dp[j - coins[i].coins_value] - ;
else
dp[j] = -;
}
}
}
for (i = ; i <= m; i++)
if (dp[i] > -) ans++;
printf("%d\n", ans);
}