本文主要是介绍UVA - 812 Trade on Verweggistan，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：首先给你个w，表示几组货物，然后给你n以及n个数表示价格，10-价格是利润
每次只能取前i个，求最多的利润对应几个货物，不超过10个解
思路：首先是简单的计算最大的利润，然后就是储存所有的解，然后深搜出所有的可能
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>
#include <set>using namespace std;const int MAXN = 100;int w, val[MAXN][MAXN];
set<int > ans;
vector<int > p[MAXN];void cal(int n, int sum) {if (n == w) {ans.insert(sum);return;}for (int i = 0; i < p[n].size(); i++) cal(n+1, sum+p[n][i]);
}void solve() {ans.clear();int valMax[MAXN], valSum, pro;valSum = 0;memset(valMax, 0, sizeof(valMax));for (int i = 0; i < w; i++) {p[i].clear();pro = 0;for (int j = 1; j <= val[i][0]; j++) {pro += 10 - val[i][j];valMax[i] = max(valMax[i], pro);}valSum += valMax[i];if (valMax[i] == 0)p[i].push_back(0);pro = 0;for (int j = 1; j <= val[i][0]; j++) {pro += 10 - val[i][j];if (valMax[i] == pro)p[i].push_back(j);}}cal(0, 0);printf("Maximum profit is %d.\n", valSum);printf("Number of pruls to buy:");int cnt = 0;for (set<int>::iterator i = ans.begin(); i != ans.end() && cnt != 10; i++, cnt++) printf(" %d", *i);printf("\n");
}int main() {int t = 0;while (scanf("%d", &w) != EOF && w) {int b;for (int i = 0; i < w; i++) {scanf("%d", &val[i][0]);for (int j = 1; j <= val[i][0]; j++)scanf("%d", &val[i][j]);}if (t)printf("\n");printf("Workyards %d\n", ++t);solve();}return 0;
}这篇关于UVA - 812 Trade on Verweggistan的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
