洛谷P2240部分背包问题

2024-12-18 - 第 39 篇
洛谷贪心算法题单 - 贪心算法 - 学习笔记
作者(Author): 郑龙浩 / 仟濹(CSND账号名)

P2240【深基12.例1】部分背包问题

题目描述

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

输入格式

第一行两个整数 N , T N,T N,T。

接下来 N N N 行，每行两个整数 m i , v i m_i,v_i mi,vi。

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

240.00

思路：

使用结构体存储每个金币的重量、价值和重量价值比(单位价值)
对结构体数组进行排序，按金币重量价值比(单位价值) 降序排序
循环遍历结构体数组，将重量价值比(单位价值) 高的金币先存入背包
当存入的重量 == 背包容量时，退出循环 --> 此时背包刚好装满，无需再进行多余的计算
当存入的重量 > 背包容量时这部分挺重要的，主要是将金币【切割】存入背包中
5.1 既然已经超重了，那么无非就是一点点切，直到将金币切到不超重为止，麻烦的地方在于“如何确定切下一个重量的金币【值多少钱】”
5.2 所以思路就是，循环，直到存入的重量 <= 背包载重为止，那么
每次循环
(1) 重量 -1 个重量单位
(2) 总价值 - 1 个重量单位的价值 --> 即重量价值比(单位价值)
打印结果

代码:

// 洛谷P2240 背包部分问题
// 贪心算法
// 1. 使用结构体存储每个金币的 重量、价值和 重量价值比(单位价值)
// 2. 对结构体数组进行排序，按 金币重量价值比(单位价值) 降序排序
// 3. 循环遍历结构体数组，将 重量价值比(单位价值) 高的 金币 先存入背包
// 4. 当 存入的重量 == 背包容量时，退出循环 --> 此时背包刚好装满，无需再进行多余的计算
// 5. 当 存入的重量 > 背包容量时  这部分挺重要的，主要是 将金币【切割】存入背包中
//    5.1 既然已经超重了，那么无非就是一点点切，直到将金币切到不超重为止，麻烦的地方在于“如何确定切下一个重量的金币【值多少钱】”
//    5.2 所以思路就是，循环，直到 存入的重量 <= 背包载重为止，那么
        // 每次循环
        // (1) 重量 -1 个重量单位
        // (2) 总价值 - 1 个重量单位 的价值 --> 即重量价值比(单位价值)
// 6. 打印结果
#include <iostream>
#include <algorithm>
using namespace std;
// 存放金币 数据
struct ddd{
    int weight; // 重量 --> 其实可以看为 某种价值的 数量
    int value; // 价值
    double rate; // 金币重量价值比 - 单位价值
};
// 排序 比较函数 --> 按 金币重量价值比 降序排序
bool cmp( ddd a, ddd b ){
    return a.rate > b.rate;
}
void display( ddd a[], int num ){
    for( int i = 0; i < num; i ++ ){
        cout << a[ i ].weight << " " << a[ i ].value << " " << a[ i ].rate << endl;
    }
    cout << endl;
}
int main( void ){
    ddd data[ 100 ]; // 金币数量 <= 100
    int num, bag; // num 个金币 bag 为背包存储的最大重量
    double sum_value = 0; // 已存入背包的总价值
    int sum_weight = 0; // 已存入背包的总重量
    cin >> num >> bag; // 输入 金币数量 和 背包容量
    for ( int i = 0; i < num; i ++ ){
        cin >> data[ i ].weight >> data[ i ].value; // 输入 每个的 金币的重量 和 金币的价值
        data[ i ].rate = (double)data[ i ].value / (double)data[ i ].weight; // 计算 金币重量价值比
    }
    // 将 价值比高的 排在前边
    sort( data, data + num, cmp ); // 排序
    // 检测
    // display( data, num );

    for( int i = 0; i < num; i ++ ){
        sum_weight += data[ i ].weight; // 先存入 价值比高的 金币
        sum_value += data[ i ].value; // 每次 将 该金币所值的所有价值存入 背包总价值中
        if( sum_weight == bag ) // 当 存入的重量 等于 背包容量时
            break;
        else if( sum_weight > bag ){ // 当 存入的重量 > 背包承重 时,则证明 需要将最后金币进行切割或者去掉
            // 变量保护
            int last_gold_weight = data[ i ].weight; // 记录 最后存入的金币重量(变量保护) -> 循环中会变
            double last_gold_rate = data[ i ].rate; // 记录 最后存入“价值比”(变量保护) -> 循环中不会变

            // 将最后存入的金币进行 “逐步切割” 直到 “存入重量 <= 背包承重” 在此期间必须保证金币重量>0
            while( sum_weight > bag && last_gold_weight > 0 ){
                last_gold_weight --; // 每次 “切割” 1 单位重量
                sum_weight --; // 每次 “切割” 1 单位重量
                sum_value -= last_gold_rate; // 每次 “切割” 1 单位价值
            }
            // 记得break --> 否则会计算后边的内容，然而此时背包已经装满，所以必须退出循环，刚开始忘记写break了，导致结果出错
            break;
        }
    }
    // cout << sum_weight << " " <<sum_value << endl; // 打印结果
    printf( "%.2f", sum_value );
    return 0;
}

标签：背包,洛谷,weight,重量,P2240,存入,金币,价值
From： https://blog.csdn.net/m0_60605989/article/details/144571880