[每日算法]部分背包问题

题目描述

阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 N(N≤100) 堆金币，第 i 堆金币的总重量和总价值分别是m_i,v_i(1≤m_i,v_i≤100)。阿里巴巴有一个承重量为T(T≤1000) 的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？

输入格式

第一行两个整数 N,T。

接下来 N 行，每行两个整数 m_i,v_i。

输出格式

一个实数表示答案，输出两位小数。

输入输出样例

样例#1	输出#1
4 50 10 60 20 100 30 120 15 45	240.00

题解

这道题为部分背包问题，金币是可以任意分割的，因此可以用贪心的思想进行求解。首先要计算出每份金币的单位价格，然后将其放入一个优先级队列，单位价格越高的金币堆优先级越高。然后按照优先级队列的顺序取金币即可，直到背包装不下或者所有金币被拿完才停止。当处理最后一份金币时，如果背包不能完全装下，就分割这一堆金币，把背包装满即可。

源代码

#include <iostream>
#include <queue>

#include <iomanip>
using namespace std;

//计算单位价格
float unitPrice(int weight, int value)
{
    return float(value) / float(weight);
}

struct Gold
{
    int weight;        //重量
    int value;        //总价值
    float uPrice;    //价值比

    Gold() {};
    Gold(int w, int v)
    {
        weight = w;
        value = v;
        uPrice = unitPrice(w, v);
    }
    //价值比越高优先级越高
    friend bool operator < (Gold a, Gold b) 
    {
        return  a.uPrice < b.uPrice;
    }

};

//第一个参数为金币的堆数，第二参数为背包的承重，第三个参数存有每堆金币的具体信息
float maxMoney(int N, int T, priority_queue<Gold> detail)
{
    //初始状态剩余重量为N，剩余金币堆数为N
    int remainWeight = T, remainHeap = N;
    float totalMoney = 0;
    Gold curGold;
    //背包未装满并且有剩余金币时
    while (remainWeight > 0 && remainHeap > 0)
    {//获取价值比最高的金币
        curGold = detail.top();
        if (remainWeight >= curGold.weight)
        {//剩余重量大于这堆金币的重量,全部装入
            detail.pop();
            remainWeight -= curGold.weight;
            remainHeap--;
            totalMoney += curGold.value;
        }
        else
        {//不能完全把这块金币装入需要拆分
            totalMoney += curGold.uPrice * remainWeight;
            curGold.weight -= remainWeight;
            detail.pop();
            detail.push(curGold);
            remainWeight = 0;
        }
    }
    return totalMoney;
}

int main()
{
    priority_queue<Gold> price;
    int N, T, m, v;
    cin >> N >> T;    //n为金币的堆数
    //数据装载进优先级队列
    for (int i = 0;i < N;i++)
    {
        cin >> m >> v;
        Gold* node = new Gold(m, v);
        price.push(*node);
    }
    //保留两位小数
    cout << fixed << setprecision(2);
    cout << maxMoney(N, T, price);

    return 0;
}