【洛谷 P2240】【深基12.例1】部分背包问题 题解(贪心算法)

简介: **深基12.例1**是部分背包问题,$N$堆金币,每堆$(m_i, v_i)$,$T$承重限制。按金币单价降序装包,保证价值最大化。输入$N,T$及每堆金币详情,输出两位小数的最大价值。示例:输入$4,50$,输出$240.00$。AC代码使用C++,通过排序和迭代实现。

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

题目描述

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

4 50
10 60
20 100
30 120
15 45

样例输出 #1

240.00

思路

按金币单价对每堆金币从大到小排序,然后按金币单价将一堆堆金币放入背包。当若下一堆金币放不下背包时,计算背包剩余空间,将下一堆金币分割后,得到与背包剩余空间相等的金币重量的一小堆金币,用其装满背包。

AC代码

#include <iostream>
#include <iomanip>
#include <algorithm>
#define AUTHOR "HEX9CF"
using namespace std;

const int maxn = 100005;

struct S{
   
    int m;
    double v;
}g[maxn];

bool cmp(S x, S y){
   
    return (x.v / x.m) > (y.v / y.m);
}

int main(){
   
    int n, t;
    cin >> n >> t;
    for(int i = 0; i < n; i++){
   
        cin >> g[i].m >> g[i].v;
    }
    sort(g, g + n, cmp);
    struct S h = {
   0, 0};
    int ii = 0;
    while(h.m + g[ii].m <= t && ii < n){
   
        h.m += g[ii].m;
        h.v += g[ii].v;
        ii++;
    }
    if(h.m < t && ii < n){
   
        int l = t - h.m;
        h.v += l * g[ii].v / g[ii].m;
    }
    cout << setiosflags(ios::fixed) << setprecision(2) << h.v << endl;
    return 0;
}
目录
相关文章
|
13天前
|
机器学习/深度学习 存储 算法
动态规划算法深度解析:0-1背包问题
0-1背包问题是经典的组合优化问题,目标是在给定物品重量和价值及背包容量限制下,选取物品使得总价值最大化且每个物品仅能被选一次。该问题通常采用动态规划方法解决,通过构建二维状态表dp[i][j]记录前i个物品在容量j时的最大价值,利用状态转移方程避免重复计算子问题,从而高效求解最优解。
215 1
|
13天前
|
算法 搜索推荐 Java
贪心算法:部分背包问题深度解析
该Java代码基于贪心算法求解分数背包问题,通过按单位价值降序排序,优先装入高价值物品,并支持部分装入。核心包括冒泡排序优化、分阶段装入策略及精度控制,体现贪心选择性质,适用于可分割资源的最优化场景。
126 1
贪心算法:部分背包问题深度解析
|
9月前
|
算法 Java C++
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
219 5
|
12月前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
503 2
动态规划算法学习三:0-1背包问题
|
12月前
|
存储 算法
算法之背包问题
本文讨论了可分背包问题和0-1背包问题的区别及解决方法,其中可分背包问题可以使用贪心算法解决,而0-1背包问题则通常采用动态规划方法来找到最大价值的解决方案。
143 0
算法之背包问题
|
12月前
|
算法 C++
【算法】DP背包问题(C/C++)
【算法】DP背包问题(C/C++)
|
算法 Python
贪心算法-分数背包问题(Python实现)
贪心算法-分数背包问题(Python实现)
183 0
|
算法 Java 测试技术
算法设计(动态规划实验报告) 基于动态规划的背包问题、Warshall算法和Floyd算法
这篇文章介绍了基于动态规划法的三种算法:解决背包问题的递归和自底向上实现、Warshall算法和Floyd算法,并提供了它们的伪代码、Java源代码实现以及时间效率分析。
算法设计(动态规划实验报告) 基于动态规划的背包问题、Warshall算法和Floyd算法
|
算法 Java 决策智能
Java数据结构与算法:动态规划之背包问题
Java数据结构与算法:动态规划之背包问题
|
算法
算法系列--动态规划--背包问题(2)--01背包拓展题目(下)
算法系列--动态规划--背包问题(2)--01背包拓展题目(下)
104 0
算法系列--动态规划--背包问题(2)--01背包拓展题目(下)

热门文章

最新文章