小欧逛商店

[题目链接](https://www.nowcoder.com/practice/919086dc716a466ba8284d5c749e8c15)

思路

本题是一道模拟/贪心题。小欧按从左到右的顺序逛商店，每遇到一个商品就判断背包剩余容量是否能装下：

  1. 如果当前商品的体积 剩余容量，就买下它，剩余容量减少，总价值增加。
  2. 如果装不下，就跳过这个商品。

注意：小欧是贪心地按顺序购买，不是经典的 0-1 背包求最优解。只需按顺序扫描一遍即可。

注意事项

数据范围中商品数量可达 ，价值可达 ，因此总价值可能达到 级别，超过 32 位整数范围。C++ 中需要使用 long long，Java 中需要使用 long。

举例

以样例 n=3, cap=5 为例：

商品 体积 价值 剩余容量 操作 总价值
1 4 3 5 买入，容量变为 1 3
2 2 5 1 装不下，跳过 3
3 1 3 1 买入，容量变为 0 6

最终答案为 。

代码

#include <iostream>
using namespace std;

int main() {
    long long n, cap;
    cin >> n >> cap;
    long long totalValue = 0;
    for (long long i = 0; i < n; i++) {
        long long v, w;
        cin >> v >> w;
        if (v <= cap) {
            cap -= v;
            totalValue += w;
        }
    }
    cout << totalValue << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long cap = sc.nextLong();
        long totalValue = 0;
        for (int i = 0; i < n; i++) {
            long v = sc.nextLong();
            long w = sc.nextLong();
            if (v <= cap) {
                cap -= v;
                totalValue += w;
            }
        }
        System.out.println(totalValue);
    }
}

n, cap = map(int, input().split())
total = 0
for _ in range(n):
    v, w = map(int, input().split())
    if v <= cap:
        cap -= v
        total += w
print(total)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const [n, cap] = lines[0].split(' ').map(Number);
    let remaining = cap;
    let total = 0;
    for (let i = 1; i <= n; i++) {
        const [v, w] = lines[i].split(' ').map(Number);
        if (v <= remaining) {
            remaining -= v;
            total += w;
        }
    }
    console.log(total);
});

复杂度

  • 时间复杂度：，只需遍历一次所有商品。
  • 空间复杂度：，只使用常数个变量。