用动态规划求0-1背包问题，n=5,c=15,w={12,1,4,1,2},v={4,2,10,1,2}.求背包所得的最大价值和最优解，c++代码及计算过程

对于动态规划求解0-1背包问题，我们需要定义一个二维数组dp[i][j]，表示前i个物品放入容量为j的背包中所能得到的最大价值。则状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) (j >= w[i])

其中，w[i]表示第i个物品的重量，v[i]表示第i个物品的价值。

代码如下：

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

int main()
{
    int n = 5, c = 15;
    vector<int> w = {12, 1, 4, 1, 2};
    vector<int> v = {4, 2, 10, 1, 2};

    vector<vector<int>> dp(n+1, vector<int>(c+1, 0));

    // 动态规划求解
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= c; j++)
        {
            if(j >= w[i-1])
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
            else
                dp[i][j] = dp[i-1][j];
        }
    }

    // 输出最大价值
    cout << "最大价值：" << dp[n][c] << endl;

    // 输出最优解
    vector<int> ans;
    int i = n, j = c;
    while(i > 0 && j > 0)
    {
        if(dp[i][j] > dp[i-1][j])
        {
            ans.push_back(i-1);
            j -= w[i-1];
        }
        i--;
    }
    cout << "最优解：";
    for(int i = ans.size()-1; i >= 0; i--)
        cout << ans[i] << " ";
    cout << endl;

    return 0;
}

计算过程如下：

第一步，初始化dp数组：

dp[0][0] = 0
dp[0][1] = 0
dp[0][2] = 0
dp[0][3] = 0
dp[0][4] = 0
dp[0][5] = 0
dp[0][6] = 0
dp[0][7] = 0
dp[0][8] = 0
dp[0][9] = 0
dp[0][10] = 0
dp[0][11] = 0
dp[0][12] = 0
dp[0][13] = 0
dp[0][14] = 0
dp[0][15] = 0

第二步，填充dp数组：

dp[1][0] = 0
dp[1][1] = 0
dp[1][2] = 0
dp[1][3] = 0
dp[1][4] = 0
dp[1][5] = 0
dp[1][6] = 0
dp[1][7] = 0
dp[1][8] = 0
dp[1][9] = 0
dp[1][10] = 0
dp[1][11] = 0
dp[1][12] = 4
dp[1][13] = 4
dp[1][14] = 4
dp[1][15] = 4

dp[2][0] = 0
dp[2][1] = 2
dp[2][2] = 2
dp[2][3] = 2
dp[2][4] = 2
dp[2][5] = 2
dp[2][6] = 2
dp[2][7] = 2
dp[2][8] = 2
dp[2][9] = 2
dp[2][10] = 2
dp[2][11] = 2
dp[2][12] = 4
dp[2][13] = 6
dp[2][14] = 6
dp[2][15] = 6

dp[3][0] = 0
dp[3][1] = 2
dp[3][2] = 2
dp[3][3] = 2
dp[3][4] = 10
dp[3][5] = 12
dp[3][6] = 12
dp[3][7] = 12
dp[3][8] = 12
dp[3][9] = 12
dp[3][10] = 12
dp[3][11] = 12
dp[3][12] = 14
dp[3][13] = 16
dp[3][14] = 16
dp[3][15] = 18

dp[4][0] = 0
dp[4][1] = 2
dp[4][2] = 2
dp[4][3] = 3
dp[4][4] = 10
dp[4][5] = 12
dp[4][6] = 12
dp[4][7] = 13
dp[4][8] = 13
dp[4][9] = 13
dp[4][10] = 13
dp[4][11] = 14
dp[4][12] = 14
dp[4][13] = 16
dp[4][14] = 18
dp[4][15] = 19

dp[5][0] = 0
dp[5][1] = 2
dp[5][2] = 2
dp[5][3] = 3
dp[5][4] = 10
dp[5][5] = 12
dp[5][6] = 12
dp[5][7] = 13
dp[5][8] = 13
dp[5][9] = 15
dp[5][10] = 15
dp[5][11] = 16
dp[5][12] = 16
dp[5][13] = 18
dp[5][14] = 20
dp[5][15] = 21

第三步，输出最大价值和最优解：

最大价值：21
最优解：2 4 

因此，在背包容量为15时，最大价值为21，最优解为将第2个物品和第4个物品放入背包中。