2052 装船问题

短命女 2022-02-16 15:43 189阅读 0赞

### 装船问题 ###

Time Limit: 1000 ms Memory Limit: 65536 KiB

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

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

#include<bits/stdc++.h>
    using namespace std;
    
    struct node{
      int pi,wi,vi;  //总价值pi ,总重量wi,价重比vi
    }a[12];
    
    bool cmp(struct node x, struct node y){
      return x.vi>y.vi;
    }
    
    int main()
    {
        int sum,val=0;
        std::cin >> sum;
        for(int i = 0; i < 10; i++){
          std::cin >> a[i].pi >> a[i].wi;
          a[i].vi = a[i].pi / a[i].wi;  //计算价重比vi
        }
    
        sort(a, a+10, cmp);
    
        for (int i = 0; i < 10; i++) {
          if (sum >= a[i].wi){
            val += a[i].pi;
            sum -= a[i].wi;       //剩余可装重量
          }
          else{                    //最后装下的部分 价值=价重比*重量
            val += a[i].vi*sum;
            break;
          }
        }
        std::cout << val << '\n';
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，189人围观）

还没有评论，来说两句吧...

相关阅读

相关装船问题

欢迎访问我的个人技术博客：[苦酒的个人小站][Link 1] 装船问题 Problem Description 王小二毕业后从事船运规划工作，吉祥号货轮的最大载重量为

我不是女神ヾ/ 2023年06月13日 11:12/ 0 赞/ 1 阅读

相关装船问题

Problem Description 王小二毕业后从事船运规划工作，吉祥号货轮的最大载重量为M吨，有10种货物可以装船。第i种货物有wi吨，总价值是pi。王小二的任务是

深藏阁楼爱情的钟/ 2022年07月13日 12:38/ 0 赞/ 167 阅读

相关贪心装船问题

装船问题 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [Statistic][] Problem De

向右看齐/ 2022年07月12日 06:17/ 0 赞/ 186 阅读

相关装船问题(快排解决

装船问题 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Description

你的名字/ 2022年07月12日 02:44/ 0 赞/ 162 阅读

相关装船问题

Problem Description 王小二毕业后从事船运规划工作，吉祥号货轮的最大载重量为M吨，有10种货物可以装船。第i种货物有wi吨，总价值是pi。王小二的任务是

港控/mmm°/ 2022年07月12日 02:37/ 0 赞/ 211 阅读

相关装船问题——贪心算法思想

Think: 1不要与背包问题混淆，题意挑选货物若干吨而不是挑选多少种货物 [sdut题目链接][sdut] 装船问题 Time Limit: 1000MS Mem

╰半橙微兮°/ 2022年06月17日 03:37/ 0 赞/ 202 阅读

相关 C语言贪心装船问题

装船问题 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [Statistic][] Problem Des

你的名字/ 2022年06月01日 11:09/ 0 赞/ 186 阅读

相关装船问题

Problem Description 王小二毕业后从事船运规划工作，吉祥号货轮的最大载重量为M吨，有10种货物可以装船。第i种货物有wi吨，总价值是pi。王小二的任务是从1

淩亂°似流年/ 2022年05月16日 13:09/ 0 赞/ 181 阅读

相关装船问题

装船问题 Time Limit: 1000 ms Memory Limit: 65536 KiB [Submit][] [Statistic][] Problem D

偏执的太偏执、/ 2022年02月25日 07:24/ 0 赞/ 200 阅读

相关 2052 装船问题

装船问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 王小二毕业后从事船运规划工作

短命女/ 2022年02月16日 15:43/ 0 赞/ 190 阅读