[已解决]还是看不太懂，求大佬帮帮（解释一下它的状态转移方程）

叶落了

/*
在英国，货币是由英镑 ￡，便士 p 构成的。一共有八种钱币在流通：

1p, 2p, 5p, 10p, 20p, 50p, ￡1 (100p) 和 ￡2 (200p).
要构造 ￡2 可以用如下方法：

1×￡1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

允许使用任意数目的钱币，一共有多少种构造 ￡2 的方法？
动态规划
答案：73682
*/
#include <iostream>
using namespace std;

int a[8] = { 1, 2, 5, 10, 20, 50, 100,200 };//各种币值
long long f[201] = { 1 };//f[k]表示k值可以有多少种构造方式

int main(void)
{
  //动态转移方程
  for (int i = 0; i < 8; ++i)//对钞票的种类进行枚举
  {
    for (int j = 200; j >= a[i]; --j)//对要构造的值j进行枚举
    {
      for (int k = 1; k * a[i] <= j; ++k)//对构造的钞票张数进行枚举
        f[j] += f[j - k * a[i]];//在原来基础上添加k张值为a[i]便士的钞票
    }
  }
  cout << f[200] << endl;
  return 0;
}

最佳答案

月排行榜 / 总排行榜

陶远航

2023-7-6 19:22:10

我明白这个问题可能有点难以理解，这个问题是关于英国货币系统的，要求计算有多少种方法可以用 8 种不同面额的钱币构造 出 &#163;2。这个问题可以通过动态规划来解决。下面是代码的解释：

首先，定义一个数组 `a[8]` 来存储 8 种货币的面额（以便士表示）：

int a[8] = { 1, 2, 5, 10, 20, 50, 100, 200 };

然后定义一个数组 `f[201]`，其中 `f[k]` 表示用上述货币构造出 k 便士的方法数。初始化 `f[0]` 为 1，表示构造 0 便士有一种方 法（即不使用任何货币）。

long long f[201] = { 1 };

接下来是动态规划的核心部分。我们使用三层循环来更新数组 `f`：

1. 第一层循环遍历所有的货币面额 `a[i]`：

for (int i = 0; i < 8; ++i)

2. 第二层循环遍历所有可能的目标值 `j`（从 200 便士到当前面额，倒序）：

for (int j = 200; j >= a[i]; --j)

3. 第三层循环遍历所有可能使用的当前面额钞票数量 `k`（从 1 到 `j / a[i]`）：

for (int k = 1; k * a[i] <= j; ++k)

在这三层循环中，我们根据当前的货币面额 `a[i]` 和钞票数量 `k` 更新 `f[j]`：

f[j] += f[j - k * a[i]];

这个状态转移方程的含义是：当我们用 `k` 张面额为 `a[i]` 的钞票构造 `j` 时，我们可以在原来构造 `j - k * a` 的基础上添加这 `k` 张钞票。

最后，输出 `f[200]`，即构造 &#163;2（200 便士）的方法数：

cout << f[200] << endl;

[/i][/i][/i][/i]

跳转到最佳答案楼层

陶远航

我明白这个问题可能有点难以理解，这个问题是关于英国货币系统的，要求计算有多少种方法可以用 8 种不同面额的钱币构造 出 &#163;2。这个问题可以通过动态规划来解决。下面是代码的解释：

首先，定义一个数组 `a[8]` 来存储 8 种货币的面额（以便士表示）：

int a[8] = { 1, 2, 5, 10, 20, 50, 100, 200 };

然后定义一个数组 `f[201]`，其中 `f[k]` 表示用上述货币构造出 k 便士的方法数。初始化 `f[0]` 为 1，表示构造 0 便士有一种方 法（即不使用任何货币）。

long long f[201] = { 1 };

接下来是动态规划的核心部分。我们使用三层循环来更新数组 `f`：

1. 第一层循环遍历所有的货币面额 `a[i]`：

for (int i = 0; i < 8; ++i)

2. 第二层循环遍历所有可能的目标值 `j`（从 200 便士到当前面额，倒序）：

for (int j = 200; j >= a[i]; --j)

3. 第三层循环遍历所有可能使用的当前面额钞票数量 `k`（从 1 到 `j / a[i]`）：

for (int k = 1; k * a[i] <= j; ++k)

在这三层循环中，我们根据当前的货币面额 `a[i]` 和钞票数量 `k` 更新 `f[j]`：

f[j] += f[j - k * a[i]];

这个状态转移方程的含义是：当我们用 `k` 张面额为 `a[i]` 的钞票构造 `j` 时，我们可以在原来构造 `j - k * a` 的基础上添加这 `k` 张钞票。

最后，输出 `f[200]`，即构造 &#163;2（200 便士）的方法数：

cout << f[200] << endl;

[/i][/i][/i][/i]

sfqxx

这段代码使用动态规划的思想来解决一个货币组合问题，即如何用一系列英镑和便士的钞票来构造给定金额的方法数。

首先，定义一个数组a，表示八种钱币的面值，分别为1p, 2p, 5p, 10p, 20p, 50p, ￡1 (100p) 和 ￡2 (200p)。

接着，定义一个数组f，其中f[k]表示金额k可以由多少种方式构造。

然后，通过动态转移方程计算f数组的值。具体过程如下：

- 对钞票的种类进行枚举，循环变量为i。
- 对要构造的值j进行枚举，循环变量为j，初始值为200（要构造的总金额为￡2）。
- 对构造的钞票张数进行枚举，循环变量为k，从1开始到每次所需钞票的最大张数，即k * a[i] <= j。
- 在原来基础上添加k张面值为a[i]的钞票，即 f[j] += f[j - k * a[i]]。

最后，输出f[200]的值，即可得到构造￡2的方法数。

在这个特定的问题中，通过计算得出答案为73682。

isdkz

这段代码使用动态规划的思想来计算构造￡2的方法数。

首先，定义一个数组a来表示8种不同的币值，分别是1p, 2p, 5p, 10p, 20p, 50p, ￡1 (100p) 和 ￡2 (200p)。

然后，定义一个数组f来表示从0到200每个金额可以有多少种构造方式，初始值为1（只有0这个金额可以有一种构造方式）。

接下来，使用三层循环进行动态转移。第一层循环遍历8种币值，第二层循环遍历要构造的金额j（从200到币值a[ i]），第三层循环遍历构造的钞票张数k（从1开始，直到k * a[ i]小于等于j）。

在每次循环中，f[j]的值等于f[j]加上f[j - k * a[ i]]。这表示在原来的构造方式基础上，添加k张币值为a[ i]的钞票，得到金额为j的构造方式数。

最后，输出f[200]的值，即为构造￡2的方法数。

对于给定的代码，输出结果为73682。表示一共有73682种方式可以构造￡2。

编程追风梦

手动回答吧，脚本出毛病了


代码用动态规划解决构造2英镑的问题，统计构造方式的数量

状态转移方程可以这么解释：

for (int i = 0; i < 8; ++i) {
  for (int j = 200; j >= a[i]; --j) {
    for (int k = 1; k * a[i] <= j; ++k) {
      f[j] += f[j - k * a[i]];
    }
  }
}

1. 外层循环 `for (int i = 0; i < 8; ++i)`：对钞票的种类进行枚举，一共有8种钞票，从小面值到大面值进行循环

2. 第二层循环 `for (int j = 200; j >= a[i]; --j)`：对要构造的值 `j` 进行枚举，从200开始递减到当前钞票面值 `a[i]`，因为如果要构造的值小于当前钞票面值，那么构造方式就为0

3. 第三层循环 `for (int k = 1; k * a[i] <= j; ++k)`：对构造的钞票张数进行枚举，从1开始递增，每次增加1张钞票，直到钞票面值的张数乘以 `k` 大于 `j` 为止

4. 状态转移方程 `f[j] += f[j - k * a[i]]`：通过当前面值 `a[i]` 的钞票，计算构造值 `j` 的方法数量，`f[j - k * a[i]]` 表示在原来基础上添加 `k` 张面值为 `a[i]` 的钞票，因此将这个数量累加到 `f[j]` 上

最后，输出 `f[200]` 的值，即构造2英镑的方法数量

这个状态转移方程的思想是将问题分解为更小的子问题，通过不同面值的钞票进行组合，逐步计算构造不同金额的方法数量，最终得到构造2英镑的总方法数量



求求给个最佳答案吧