二维形式的dp数组中还原方案

#include <bits/stdc++.h>
using namespace std;
int n, m;        // 物品数量、背包大小
int v[35];       // v[i]：第i件物品的大小
int w[35];       // w[i]：第i件物品的价值
int dp[35][205]; // dp[i][j]：前i件物品在j的体积下的最大价值
vector<int> ans; // 记录最终方案（选择了哪些物品）
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    // 求解dp数组
    for (int i = 1; i <= n; i++) // 物品
    {
        for (int j = 1; j <= m; j++) // 体积
        {
            // 求解 dp[i][j]，考虑是否选用了第i件物品
            // 如果没选用：答案为前 i-1 件物品在 j 的体积下的最大价值
            // 如果选用：第i件物品占用 v[i] 的背包大小
            //          前 i-1 件物品就只能使用 j-v[i] 的体积了
            if (j < v[i]) // 不能选用第i件物品
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j], w[i] + dp[i - 1][j - v[i]]);
        }
    }
    // 输出
    cout << dp[n][m] << "\n";
    for (int i = n, j = m; i >= 1; i--)
    {
        if (dp[i][j] != dp[i - 1][j])
        {
            ans.push_back(i);
            j -= v[i];
        }
    }
    cout << ans.size() << "\n";
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << " ";
    return 0;
}

记录最大价值的同时，记录方案

#include <bits/stdc++.h>
using namespace std;
int n, m;             // 物品数量、背包大小
int v[35];            // v[i]：第i件物品的大小
int w[35];            // w[i]：第i件物品的价值
int dp[205];          // dp[j]：当前在j的体积下的最大价值
vector<int> ans[205]; // ans[j]: 记录在j的体积下的最大价值的方案（选择了哪些物品）
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    // 求解dp数组
    for (int i = 1; i <= n; i++)        // 物品
        for (int j = m; j >= v[i]; j--) // 体积
            if (dp[j - v[i]] + w[i] > dp[j])
            {
                dp[j] = dp[j - v[i]] + w[i];
                ans[j] = ans[j - v[i]];
                ans[j].push_back(i);
            }
    // 输出
    cout << dp[m] << "\n";
    cout << ans[m].size() << "\n";
    for (int i = 0; i < ans[m].size(); i++)
        cout << ans[m][i] << " ";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 35, M = 205;
int m, n, v[N], w[N], dp[N][M], ans[N], t; // dp[i][j] 前i个物品在j的背包容量下价值最大值
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> m >> n;
	for (int i = 1; i <= n; i++)
		cin >> v[i] >> w[i];
	// 使用二维数组DP 便于输出路径
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (v[i] > j)
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
		}
	}
	int res = dp[n][m];
	// 输出路径
	while (n && m)
	{
		if (dp[n][m] == dp[n - 1][m - v[n]] + w[n]) // 判断是否选择了当前物品
			ans[++t] = n, m -= v[n];				// 记录路径 更新当前总价值
		n--;
	}
	cout << res << endl
		 << t << endl;
	for (int i = t; i >= 1; i--)
		cout << ans[i] << " ";
}

#include<bits/stdc++.h>
using namespace std;
int dp[35][205];//dp[i][j]前i个物品，占用j个单位空间
int n,m;
int v[35];//第i件物品的体积
int w[35];//第i件物品的价值
vector <int> e[35][205];//前i个数，总共j空间，塞了哪些数
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)//考虑第i件物品选不选
for(int j=1;j<=m;j++)
{
if(j-v[i]>=0)
{
//dp[i][j]=max(dp[i-1][j-v[i]]+w[i],dp[i-1][j]);
if(dp[i-1][j-v[i]]+w[i]>=dp[i-1][j])
{
dp[i][j]=dp[i-1][j-v[i]]+w[i];
//把e[i-1][j-v[i]]的所有点都压入e[i][j]
for(int k=0;k<e[i-1][j-v[i]].size();k++)
e[i][j].push_back(e[i-1][j-v[i]][k]);
e[i][j].push_back(i);
}
else
{
for(int k=0;k<e[i-1][j].size();k++)
e[i][j].push_back(e[i-1][j][k]);
dp[i][j]=max(dp[i-1][j-v[i]]+w[i],dp[i-1][j]);
}
}
else
{
for(int k=0;k<e[i-1][j].size();k++)
e[i][j].push_back(e[i-1][j][k]);
dp[i][j]=dp[i-1][j];
}
}
cout<<dp[n][m]<<endl;
cout<<e[n][m].size()<<endl;
for(int i=0;i<e[n][m].size();i++)
cout<<e[n][m][i]<<" ";
return 0;
}

赶在老师前面……