装船问题

装船问题

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(总价值/总重量),进行加减

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    #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;
    }
0%
-->