462
背包问题
背包问题
时间限制：3000 ms | 内存限制：65535 KB
难度：3
- 描述
- 现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值v和重量w（1<=v,w<=10）；如果给你一个背包它能容纳的重量为m（10<=m<=20）,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。
- 输入
- 第一行输入一个正整数n（1<=n<=5）,表示有n组测试数据；
随后有n测试数据，每组测试数据的第一行有两个正整数s，m（1<=s<=10）;s表示有s个物品。接下来的s行每行有两个正整数v，w。 - 输出
- 输出每组测试数据中背包内的物品的价值和，每次输出占一行。
- 样例输入
-
1 3 15 5 10 2 8 3 9
- 样例输出
-
65
查看代码---运行号：252528----结果：Accepted
运行时间：2012-10-06 08:46:06 | 运行人:huangyibiao
01.#include <iostream>
02.#include <cstdio>
03.#include <algorithm>
04.using
namespace std;
05.
06.struct
Goods
07.{
08.int
value;//单位价值
09.int
weight;//总重量
10.};
11.
12.int
Compare(const
void *p1, const
void *q1)
13.{
14.Goods *p = (Goods *)p1;
15.Goods *q = (Goods *)q1;
16.
17.return
p->value < q->value ? 1 : -1;
18.}
19.int
main()
20.{
21.int
sample;
22.cin >> sample;
23.
24.while
(sample --)
25.{
26.int
nNumOfGoods, //物品总数量
27.nTotalWeights;//背包容量
28.
29.scanf("%d %d",
&nNumOfGoods, &nTotalWeights);
30.Goods *g =
new Goods[nNumOfGoods];
31.
32.for
(int
i = 0; i < nNumOfGoods; i++)
33.{
34.scanf("%d %d",
&g[i].value, &g[i].weight);
35.}
36.
37.qsort(g, nNumOfGoods,
sizeof(Goods), Compare);
38.//for (int i = 0; i < nNumOfGoods; i++)
39.// printf("%d %d\n", g[i].value, g[i].weight);
40.int
nMaxMoney = 0;
41.for
(int
i = 0; i < nNumOfGoods; i++)
42.{
43.if
(nTotalWeights >= g[i].weight && nTotalWeights > 0)
44.{
45.nMaxMoney += g[i].value * g[i].weight;
46.nTotalWeights -= g[i].weight;
47.}
48.else
if (nTotalWeights > 0 && nTotalWeights < g[i].weight)
49.{
50.nMaxMoney += g[i].value * nTotalWeights;
51.break;
52.}
53.}
54.cout << nMaxMoney << endl;
55.delete
[]g;
56.}
57.return
0;
58.}
最后更新：2017-04-02 15:14:54