本文主要是介绍swustoj-Buyer(0195)（01背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
哆啦A梦班级举办个party，当然吃的东西必不可少，哆啦A梦负责采购任务，他得到了一份清单，上面注明不同食品的受欢迎程度，哆啦A梦需要用一定的价钱尽可能达到的更大的受欢迎程度！例如，瓜子的受欢迎程度为20，瓜子的价钱是50元，那么如果哆啦A梦选择买瓜子，将花费50元，但受欢迎程度增加了20。为了避免食品单调性，每种食品只能买一份，不能重复购买。 现在哆啦A梦需要知道如何采购才能达到最大的受欢迎程度，你能帮助他吗？
Description
输入数据为多组，每组输入的第一行有两个正整数M和N(M<100&&N<1000)，分别为哆啦A梦可以支配的钱数和清单上的可选择的物品种类。 接下来的N行每行有两个正整数,分别为每种物品的价钱和它的受欢迎程度（编号为1到N）。
Input
如果存在物品购买，那么输出的第一行为能够达到的最大的受欢迎程度。第二行为需要购买的物品的编号（如果有多种可能，输出字典序靠前的那种），空格分隔每个数字；如没有物品可以购买，输出只有一行，为数字0。
Output
| 1 2 3 4 5 6 | 10 4 100 5 5 5 5 5 10 10 |
Sample Input
| 1 2 3 | 10 2 3 |
Sample Output
比如有（1，3）和（2，3）两种购买方案，则输出（1，3）那组！
/**题解：01背包-用vector来记录选取的方案就行了*/#include <stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<iostream>
using namespace std;
int V, n;
int val[1005], cal[1005];
struct node
{int num;vector<int>a;
}dp[1005];
int main()
{while (cin >> V >> n){for (int i = 0; i < 1005; i++){dp[i].num = 0;dp[i].a.clear();}for (int i = 0; i < n; i++){cin >> cal[i] >> val[i];}for (int i = 0; i < n; i++){for (int j = V; j >= 0; j--){if (j >= cal[i]){if (dp[j].num >= (dp[j - cal[i]].num + val[i])){continue;}else{//每次动态更新dp[j].a.clear();dp[j].num = dp[j - cal[i]].num + val[i];for (int k = 0; k < dp[j - cal[i]].a.size(); k++){dp[j].a.push_back(dp[j - cal[i]].a[k]);}dp[j].a.push_back(i);}}}}cout << dp[V].num << endl;int sum = 0;for (int i = 0; i < dp[V].a.size(); i++){if (i != 0){cout << ' ';}cout << dp[V].a[i]+1;if (i == (dp[V].a.size() - 1))cout << endl;}}return 0;
}
这篇关于swustoj-Buyer(0195)（01背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
