递推动态规划采购商品

Question

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

输入
第一行包含两个整数 n，m；
第二行是 n 个产品的价格。

输出
购买的方案数。由于方案数可能很大，请输出其对 20232023 的余数。

样例输入
3 300
100 200 300

样例输出
3

提示
对于100%数据，1=<n<=100，1=<m<=10000，每种物品的价格是不大于 1000 的正整数。内存限制：128 MB 时间限制：1.000 S

Answer 1

这是一道典型的 0/1 背包问题，可以使用动态规划进行解决。

我们可以定义一个二维数组 dp[i][j]，其中 i 表示前 i 个产品，j 表示金额数。dp[i][j] 表示使用 j 元钱购买前 i 件物品的方案数。

则有状态转移方程：dp[i][j] = dp[i-1][j] + dp[i-1][j-v[i]]，其中 v[i] 表示第 i 个产品的价格。意思是，当不购买第 i 个产品时，方案数为 dp[i-1][j]；当购买第 i 个产品时，方案数为 dp[i-1][j-v[i]]。

最终答案为 dp[n][m]。

注意在计算过程中要对 20232023 取模，防止答案大于该数。
在修改 dp[i][j] 的值时，应该加上 dp[i][j] 自身的值。因为 dp[i-1][j-v[i]] 表示选了第 i 件物品后，剩余的总价值是 j-v[i] 的方案数，而 dp[i][j] 表示在不选第 i 件物品的前提下，总价值是 j 的方案数，所以需要将这两个方案数相加才能得到总方案数。

#include <iostream>
using namespace std;

const int MOD = 20232023;
const int MAX_N = 105;
const int MAX_M = 10005;
int n, m;
int v[MAX_N];
int dp[MAX_N][MAX_M];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        dp[i][0] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= v[i]) {
                dp[i][j] = (dp[i][j] + dp[i][j-v[i]]) % MOD; // 修改加号为加上自身的值
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

希望这次能够正确地回答您的问题，如果还有任何问题，请随时提出。