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