uva 10130 SuperSale题目大意：每组数据包括两个部分：1）货物的价值及重量 2）每个人的最大负重量。要求这些人所能带走的最大价值。解题思路：要注意的一点是，货物是有无限的，也就是不同的人可以拿相同的货物，，所以这题可以转换为01背包。把每个人的最大负重当成背包的大小，求每个人的最优解，最后相加就是答案。ll;;struct good{int v, w;};good g[1005];int p[105], dp[105];int main() {int T;scanf(“%d”, &T);while (T–) {int n, m;scanf(“%d”, &n);for (int i = 0; i < n; i++) {scanf(“%d %d”, &g[i].v, &g[i].w);}scanf(“%d”, &m);for (int i = 0; i < m; i++) {scanf(“%d”, &p[i]);}int sum = 0;for (int i = 0; i < m; i++) {int Max = 0;memset(dp, 0, sizeof(dp));for (int j = 0; j < n; j++) {for (int k = p[i]; k > 0; k–) {if ((k == g[j].w || dp[k – g[j].w]) && dp[k] < dp[k – g[j].w] + g[j].v) {dp[k] = dp[k – g[j].w] + g[j].v;if (dp[k] > Max) Max = dp[k];}}}sum += Max;}printf(“%d\n”, sum);}return 0;}
都成为命途中美丽的点缀，看天，看雪，安安静静，不言不语都是好风景。
