C++代码实现 小明是采购部的员工，现在上级派给他了一个任务，要去集市上采购部门所需的物品。现给定 n 个产品价格，和一个指定金额 m，请你帮小明计算使用指定金额 m 购买物品时共有多少种方案，每件商品可购买多次。

以下是 C++ 代码实现：

#include <iostream>
using namespace std;

const int MAXN = 1005;
int n, m, a[MAXN], dp[MAXN];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = a[i]; j <= m; j++) {
            dp[j] += dp[j - a[i]];
        }
    }

    cout << dp[m] << endl;

    return 0;
}

代码思路：

使用动态规划的思想，定义 dp[i] 表示金额为 i 时的方案数，初始化 dp[0] = 1，表示金额为 0 时只有一种方案即不购买任何商品。

对于每一个物品 i，从价格 a[i] 开始更新 dp 数组，因为小于 a[i] 的金额无法购买该物品。更新方式为：dp[j] += dp[j - a[i]]，表示金额为 j 时，可以加上 a[i] 元的物品，此时方案数要加上金额为 j - a[i] 时的方案数。

最终的结果为 dp[m]，即金额为 m 时的方案数。

相关问题

c++代码实现小明是采购部的员工，现在上级派给他了一个任务，要去集市上采购部门所需的物品。现给定 n 个产品价格，和一个指定金额 m，请你帮小明计算使用指定金额 m 购买物品时共有多少种方案，每件商品可购买多次。

以下是解决该问题的C++代码：

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    int prices[n];
    for (int i = 0; i < n; i++) {
        cin >> prices[i];
    }

    // dp[i]表示凑成i元钱的方案数
    int dp[m + 1];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;

    for (int i = 0; i < n; i++) {
        for (int j = prices[i]; j <= m; j++) {
            dp[j] += dp[j - prices[i]];
        }
    }

    cout << dp[m] << endl;
    return 0;
}

该代码使用动态规划的思想，使用dp数组记录凑成每个金额的方案数。对于每个产品的价格，从价格到总金额m遍历dp数组，更新dp[j]的值。最终输出dp[m]即为使用指定金额m购买物品的方案数。

c++代码实现 小明是采购部的员工，现在上级派给他了一个任务，要去集市上采购部门所需的物品。现给定 n 个产品价格，和一个指定金额 m，请你帮小明计算使用指定金额 m 购买物品时共有多少种方案，每件商品可购买多次。

以下是使用动态规划思想实现的 C++ 代码：

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;

    vector<int> prices(n);
    for (int i = 0; i < n; i++) {
        cin >> prices[i];
    }

    // dp[i] 表示金额为 i 时的方案数
    vector<int> dp(m + 1, 0);
    dp[0] = 1;  // 初始化金额为 0 时方案数为 1

    for (int i = 0; i < n; i++) {
        for (int j = prices[i]; j <= m; j++) {
            dp[j] += dp[j - prices[i]];
        }
    }

    cout << dp[m] << endl;

    return 0;
}

该算法的时间复杂度为 $O(nm)$，空间复杂度为 $O(m)$。