18网易春招笔试题-牛牛的背包-记忆化搜索

我就是我 2022-05-28 03:14 130阅读 0赞

/\*

牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为w。  
牛牛家里一共有n袋零食, 第i袋零食体积为v\[i\]。

牛牛想知道在总体积不超过背包容量的情况下,他一共有多少种零食放法(总体积为0也算一种放法)。

输入描述:  
输入包括两行  
第一行为两个正整数n和w(1 <= n <= 30, 1 <= w <= 2 \* 10^9),表示零食的数量和背包的容量。  
第二行n个正整数v\[i\](0 <= v\[i\] <= 10^9),表示每袋零食的体积。  
  
输出描述:  
输出一个正整数, 表示牛牛一共有多少种零食放法。  
  
输入例子1:  
3 10  
1 2 4  
输出例子1:  
8  
例子说明1:  
  
三种零食总体积小于10,于是每种零食有放入和不放入两种情况，一共有2\*2\*2 = 8种情况。

\*/

思路：

1.如果总重量小于背包重量，则存在2^n种情况。

2.什么都不放也是一种情况

3.用results<states<sumWeight,i>,sumCnt>来保存整个搜索过程。

4.每个i有放与不放两种情况，总情况数等于二者之和。

5.如果轮到放i时，发现states<sumWeight,i>已经出现过，则直接拿上一次的计算结果。

代码：

import javafx.util.Pair;
    import java.util.*;
    
    public class Main {
        private static int put(long weightRemain, int index) {
            Pair status = new Pair<>(weightRemain,index);
            return cache.getOrDefault(status,
                    put(weightRemain - weights[index],index + 1)
                            + put(weightRemain, index + 1));
        }
    
        static Map<Pair<Long, Integer>, Integer> cache;
        static long[] weights;
    
        public static void main(String args[]) {
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            long w = scanner.nextLong();
            long sumWeight = 0;
            scanner.nextLine();
            weights = new long[n];
            String[] wstr = scanner.nextLine().split(" ");
            for(int i = 0; i < n; i++) {
                weights[i] = Long.parseLong(wstr[i]);
                sumWeight += weights[i];
            }
            if(sumWeight <= w) {
                System.out.println((int)Math.pow(2,n));
                return;
            }
            cache = new HashMap<>();
            System.out.println(put(w,0));
        }
    }