部分背包问题 - Problem

阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有

N (N \leq 100)

堆金币，第

i

堆金币的总重量和总价值分别是

m_{i}, v_{i} (1 \leq m_{i}, v_{i} \leq 100)

。阿里巴巴有一个承重量为

T (T \leq 1000)

的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
struct coin {
    int m, v; // 金币堆的重量和价值
} a[110];
bool cmp(coin x, coin y) {
    return x.v * y.m > y.v * x.m; //判断单价
}
int main() {
    int n, t, c, i;
    float ans = 0;
    scanf("%d%d", &n, &t);
    c = t; // 背包的剩余容量
    for (    ;    ;    ) // 循环
        ___________ // 读入第 i 堆金币的重量和价值
    ___________ // 对这些金币按照单价从大到小排序
    for (    ;    ;    ) { // i 循环
        if (a[i].m > c) break; //如果不能完整装下就跳出
        ___________ // 背包剩余空间减去第i堆金币的体积
        ___________ // 得到的价值ans加上第i堆金币的价值
    }
    if (i < n) // 剩余空间装下部分金币
        ___________ // ans 加上第 i 个金币的部分价值。

    printf("%.2lf", ans);
    return 0;
}

Problem B: 部分背包问题

Description

Input

Output

Sample Input Copy

Sample Output Copy