装船问题

简介: 装船问题

装船问题

Problem Description

王小二毕业后从事船运规划工作,吉祥号货轮的最大载重量为M吨,有10种货物可以装船。第i种货物有wi吨,总价值是pi。王小二的任务是从10种货物中挑选若干吨上船,在满足货物总重量小于等于M的前提下,运走的货物的价重比最大。

Input

输入数据的第一行有一个正整数M(0 < M < 10000),表示所有货物最大载重量。在接下来的10行中,每行有若干个数(中间用空格分开),第i行表示的是第i种货物的货物的总价值pi ,总重量wi。(pi是wi的整数倍,0 < pi , wi < 1000)

Output

输出一个整数,表示可以得到的最大价值。

Sample Input

100

10 10

20 10

30 10

40 10

50 10

60 10

70 10

80 10

90 10

100 10

Sample Output

550

Hint

价重比:计算其价值与重量之比

思路

初看问题,好像和动态规划01背包问题差不多。

仔细分析下,这个可以选取其中的一所货物对此切割,而01背包是不可以切割的,所以这个问题解法思路有2种。

  1. 用结构体来做,排序出来的vi(总价值/总重量),进行加减
  2. 直接数组,排序出来的vi(总价值/总重量),进行加减

代码

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct node
{
    int pi;
    int wi;
    int vi;
}st[100001];
bool cmp(node a, node b)
{
    return a.vi > b.vi;
}
int main()
{
   int m;
   cin>>m;
   for(int i = 0; i < 10; i++)
   {
        cin>>st[i].pi>>st[i].wi;
        st[i].vi = st[i].pi / st[i].wi;
   }
   sort(st,st+10,cmp);
   int sum = 0;
   for(int i = 0; i < 10; i++)
   {
       if(st[i].wi <= m)
       {
           sum = sum + st[i].pi;
           m = m - st[i].wi;
       }
       else
       {
           sum = sum + m * st[i].vi;
           break;
       }
   }
    cout<<sum<<endl;
    return 0;
}


相关文章
|
开发者
语雀
简要讲述语雀文档编辑器的注册使用及个人感受
语雀
表达式语法分析——递归子程序法
表达式语法分析——递归子程序法
|
7月前
|
算法
|
7月前
|
存储 算法 C++
C++初阶(十六)优先级队列
C++初阶(十六)优先级队列
40 0
|
7月前
|
编译器 C语言 Android开发
Qt5安装及组件选择(Qt 5.12)
Qt5安装及组件选择(Qt 5.12)
769 2
|
7月前
|
关系型数据库 Java
软件工程设计原理开放封闭原则 ,具体实现及JAVA代码举例
开放封闭原则(OCP)是面向对象设计的关键,主张软件应对扩展开放、对修改封闭,以增强灵活性和可维护性。实现OCP需通过抽象和多态,如使用接口。不遵守OCP的例子是在现有类中直接添加新功能,而遵守OCP则通过创建新类实现接口或继承抽象类来扩展。Java代码展示了如何通过接口实现OCP,使得`GraphicEditor`无需修改即可支持新图形类型。遵循OCP能提升系统灵活性、可维护性和代码重用。
74 4
|
7月前
|
存储 供应链 数据可视化
一文带你认识医院信息化必备系统HIS、CIS、LIS、EMR、PACS、RIS等
医院信息系统的发展趋势是将各类医疗器械直接联机并将附近各医院乃至地区的医院信息系统联成网络。其中最关键的问题是使不同系统中的病历登记、检测、诊断指标等都要标准化。医院信息系统的高级阶段将普遍采用医疗专家系统,建立医疗质量监督和控制系统,进一步提高医疗水平和保健水平。
3975 0
一文带你认识医院信息化必备系统HIS、CIS、LIS、EMR、PACS、RIS等
|
7月前
|
数据建模 测试技术 uml
【软件工程】期末复习总结(通俗易懂,学不会来打我)
【软件工程】期末复习总结(通俗易懂,学不会来打我)
|
弹性计算 开发工具 Android开发
阿里云APP备案操作流程_亲测
阿里云APP备案操作流程_亲自测试,一共6个步骤即可完成APP备案
14074 2
|
机器学习/深度学习 并行计算 异构计算
gpu是什么和cpu的区别 模型训练
gpu是什么和cpu的区别 模型训练
775 1