NYOJ - 背包問題(貪心)

http://nyoj.top/problem/106

• 記憶體限制:64MB 時間限制:3000ms

題目描述:

現在有很多物品（它們是可以分割的），我們知道它們每個物品的機關重量的價值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

樣例輸出:

解題思路:

#include <iostream>
#include <algorithm>
using namespace std;
struct edge {
    int v, w;
}e[110];
int cmp(edge a, edge b) {
    return a.v > b.v;
}
int main()
{
    int t, s, m, ans;
    cin >> t;
    while (t--)
    {
        ans = 0;
        cin >> s >> m;
        for (int i = 0; i < s; i++)
            cin >> e[i].v >> e[i].w;
        sort(e, e + s, cmp);
        for (int i = 0; i < s; i++)
        {
            if (m >= e[i].w)
            {
                m -= e[i].w;
                ans += e[i].v * e[i].w;
            }
            else
            {
                ans += m * e[i].v;
                break;
            }
        }
        cout << ans << endl;
    }
    return 0;
}