使用位元窮舉

使用位元窮舉(有時候用遞迴更快)

利用數字的二進位之位元運算達到窮舉，速度很快

習題 Q-1-8. 子集合的和 (APCS201810, subtask)

輸入 n 個正整數，請計算各種組合中，其和最接近 P 但不超過 P 的和是多少。每個元 素可以選取或不選取但不可重複選，輸入的數字可能重複。P<=1000000009，0 < n < 26。
留言
建議修訂
編輯此處

Time limit: 1 秒

輸入格式：第一行是 n 與 P，第二行是 n 個可挑選的正整數，大小不會超過 P，同行 數字以空白間隔。

輸出格式：最接近 P 但不超過 P 的和。

範例輸入：
5 17
5 5 8 3 10

範例輸出：
16

#include <bits/stdc++.h>
using namespace std;

#define N 100

int v[N];

int main(){
    int n,m,ans=0;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>v[i];
    }



    for(int i=0;i<(1<<n);i++){
        int sum=0;
        for(int j=0;j<n;j++){
            if(i & (1<<j)){
                sum+=v[j];
            }
            if(sum>ans && sum<=m){
                ans=sum;
            }
        }
    }
    
    cout<<ans;
}

expandcollapse

1<<n就是在位元把1向右n次
如果n是5：也就是100000(32)，在第19行寫i<n所以實際上是到(1<<5)-1，也就是11111(31)

&使用方法：都是1才是1。
第12行的if(i & 1<<j)是看看i的第j個位元是否為1，如果成立便回傳1<<j，因為1<<j非0(是true)，所以執行第13行