举例一个动态规划之选数问题算法，给出问题描述，问题执行，c++代码

问题描述：给定一个长度为 n 的数组，要求从中选出若干个数，使得它们的和等于给定的目标值。假设所有数都是正整数，且每个数只能被选一次。请问是否存在这样的选数方案，若存在，输出任意一种方案。

问题执行：

1. 定义状态：设 dp[i][j] 表示在前 i 个数中选取若干个数，使得它们的和等于 j 的方案数。

2. 状态转移方程：对于第 i 个数，有两种选择：

- 不选它，此时 dp[i][j] = dp[i - 1][j]；
- 选它，此时 dp[i][j] = dp[i - 1][j - a[i]]；其中 a[i] 表示第 i 个数的值。

综上所述，状态转移方程为：

dp[i][j] = dp[i - 1][j] + dp[i - 1][j - a[i]]

3. 初始化：dp[0][0] = 1，dp[0][j] = 0（j ≠ 0），dp[i][0] = 1。

4. 最终结果：dp[n][target]，其中 n 表示数组的长度，target 表示目标值。

C++代码实现：

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

const int N = 1000;

int a[N];       // 数组
int dp[N][N];   // dp[i][j] 表示在前 i 个数中选取若干个数，使得它们的和等于 j 的方案数
vector<int> res;// 存储任意一种方案

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

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

    if (dp[n][target] == 0)
        cout << "No solution!" << endl;
    else
    {
        // 求出任意一种方案
        int i = n, j = target;
        while (j > 0)
        {
            if (dp[i][j] == dp[i - 1][j])
                i--;
            else
            {
                res.push_back(a[i]);
                j -= a[i];
                i--;
            }
        }

        // 输出方案
        for (int i = res.size() - 1; i >= 0; i--)
            cout << res[i] << " ";
        cout << endl;
    }

    return 0;
}