#include<bits/stdc++.h> #define PII pair<int, int> using namespace std; const int N = 1010, M = 110; int v[N], w[N], f[M];//v[N]是物品所需的钱财数，w[N]为物品的受欢迎程度,f[M]是在不超过当前总钱财数的前提下，物品总受欢迎程度 int n, m;//m是可以花费的最大钱财数，n为可选择的物品种类 map<int, vector<int> > buy;//记录每个背包容量下所选择的物品编号 int main() { while (cin >> m >> n) { memset(f, 0, sizeof f); buy.clear(); for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i]; for (int i = 1; i <= n; ++ i) for (int j = m; j >= v[i]; -- j) { int temp = f[j - v[i]] + w[i];//默认从包含i的情况进行考虑 // f[j] = max(f[j], temp); if (temp > f[j]) { f[j] = temp;//替换价值 buy[j] = buy[j - v[i]];//在j体积下到达最大价值的物品集合 buy[j].push_back(i);//动态存储选择的物品编号 } } cout << f[m] << endl; if (f[m]) { for (int i = 0; i < buy[m].size(); ++ i) { cout << buy[m][i]; if (i != buy[m].size() - 1) cout << " "; } cout << endl; } } return 0; }

这段代码是关于背包问题的，使用了动态规划思想，具体实现是使用一个数组 f 来记录在不超过当前总钱财数的前提下，物品总受欢迎程度。同时，使用一个 map 类型的变量 buy 记录每个背包容量下所选择的物品编号。在循环中，首先输入了最大钱财数 m 和可选择的物品种类数 n，然后输入每个物品所需的钱财数和受欢迎程度。接着进行动态规划的过程，最后输出最大的受欢迎程度和选择的物品编号。