Going to the Movies

有很多牛，Car有最大重量限制，要如何放最大重量的牛。

用暴力法，每支牛可能放可能不放，所以是2ⁿ種可能的組合。
用1 << n 直接求出 2ⁿ
用 & 運算子來產生不同的組合，


以牛編號為1 2 3為例，是否能產生所有組合：
先轉成二進位
1 -> 1
2 -> 10
3 -> 011
4 -> 100
5 -> 101
6 -> 110
7 -> 111
與1 << 0 , 1 << 1 ,1 << 2做&運算(分別為001, 010, 100)

1 可以產生 1
2 可以產生 2
3 可以產生 2 1
4 可以產生 3
5 可以產生 3 1
6 可以產生 3 2
7 可以產生 1 2 3


簡單來說因為1~1<< n 就包含了所有集合(000~111)

所以我們將每個組合順序取出之後，便詢問該組合的第一隻牛是否存在、第二隻牛是否存在.....
這就是使用&的用意了，我們使用 1 << j 會逐一產生第一隻牛存在的情況(001)、第二隻牛的存在的情況(010)、第三隻牛存在的情況(100)，只要將它與取出的組合做&運算就能求出牛是否存在，存在的話就將重量加入。

例如說組合是110 我們要試探第一隻牛在不在用001，第二隻牛在不在用010，第三隻牛在不在用100

import java.util.Scanner;



public class JAVA {

    

    public static void main(String[] args) {

        

        Scanner sc = new Scanner(System.in);

        

        while(sc.hasNext()) {

            

            int limit = sc.nextInt();

            int cowsCount = sc.nextInt();

            int[] cows = new int[cowsCount];

            

            for(int i = 0; i < cowsCount; i++) {

                cows[i] = sc.nextInt();

            }

    

            int maxWeight = 0;

            int sum = 0;

            

            for(int i = 0; i < (1<<cowsCount); i++) {

                sum = 0;

                for(int j = 0; j < cowsCount; j++) {

                    if(binToDec(Integer.toBinaryString(i & (1<<j))) > 0) {

                        sum += cows[j];

                    }

                }

                if( sum <= limit && sum > maxWeight) maxWeight = sum;

            }

            

            System.out.println(maxWeight);

        }

    }

    

    public static int binToDec(String bin) {

        

        int sum = 0;

        

        for(int i = 0; i < bin.length(); i++) {

            if(bin.charAt(i) == '1') {

                sum += (1<<(bin.length()-i-1));

            }

        }

        

        return sum;

    }

}