题解 | #牛牛们吃糖果#

0/1背包问题——java版
将糖果的数量看作背包的容量，将牛牛看作物品，牛牛需要糖果的数量看作物品的重量，牛牛的数量看作物品的价值。
至于约定，只需要将有约定的两只牛打包成一个物品，这个物品的重量为两只牛需要的糖果数量和，物品的价值为2（两只牛）。
代码如下：

public class Main{
    public static void main(String[] args){
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int m = cin.nextInt();
        int[] cow = new int[n + 1];
        for(int i = 1; i <= n; i++){
            cow[i] = cin.nextInt();
        }
        int k = cin.nextInt();
        Map<Integer, Integer> map = new HashMap<>();
        for(int x = 0; x < k; x++){
            int i = cin.nextInt();
            int j = cin.nextInt();
            map.put(i, j);
            map.put(j, i);
        }
        // 下面是合并两只有约定的牛
        // list中存放的数组有两个元素，一个是需要吃的糖果数量，一个是奶牛的数量
        List<int[]> list = new ArrayList<>();
        for(int i = 1; i <= n; i++){
            if(map.containsKey(i)){
                if(map.get(i) == null){
                    continue;
                }
                int j = map.get(i);
                int sum = cow[i] + cow[j];
                list.add(new int[]{sum, 2});
                map.put(j, null);
            }else{
                list.add(new int[]{cow[i], 1});
            }
        }
        
        // 下面是0/1背包代码，m是背包的容量
        int[] dp = new int[m + 1];
        for(int i = 0; i < list.size(); i++){
            int w = list.get(i)[0];
            int c = list.get(i)[1];
            for(int j = m; j >= w; j--){
                dp[j] = Math.max(dp[j], dp[j - w] + c);
            }
        }
        System.out.println(dp[m]);
    }
}