背包能否装满

背包能否装满

 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
 1process.stdin.resume();
 2process.stdin.setEncoding('utf-8');
 3let input = '';
 4process.stdin.on('data', (data) => {
 5    input += data;
 6});
 7process.stdin.on('end', () => {
 8    let inputArray = input.trim().split('\n');
 9    let S = parseInt(inputArray[0], 10);
10    let weights = inputArray[1].split(' ').map(Number);
11    
12    /**
13     * 待实现函数，在此函数中填入答题代码
14     * doFunc()
15     */
16    function canFillExactly(weights, target, memo = {}) {
17        if (target === 0) return true; // 如果目标重量为0，说明可以装满
18        if (target < 0) return false; // 如果目标重量小于0，说明无法装满
19        if (target in memo) return memo[target]; // 如果已经计算过，直接返回结果
20
21        // 尝试每个物品
22        for (let i = 0; i < weights.length; i++) {
23            if (canFillExactly(weights.slice(i + 1), target - weights[i], memo)) {
24                memo[target] = true;
25                return true;
26            }
27        }
28
29        memo[target] = false;
30        return false;
31    }
32
33    let result = canFillExactly(weights, S) ? "YES" : "NO";
34    console.log(result);
35    process.exit();
36});

Copyright ©2010-2022 比特日记 All Rights Reserved.

Powered By 可尔物语

浙ICP备11005866号-12