louisfghbvc的部落格

題目連結:   https://onlinejudge.org/external/124/12455.pdf

題目大意: 給你目標，問你能不能用這些酒容量加總剛剛好達到目標值 。 

思路:  法1，Subset， O(2^p * p)， 枚舉全部情況0 ~ 2^p - 1。Bit位元運算，0表示不取，1表示取那個Bar。 比如 0101 就是 取第二個跟第四個bar，

法2，01背包問題，每個Bar放與不放，重量只有1000。直接一維陣列(二維也可以)。並從後面往前面運算(重量從最大到最小，才不會無限取)。

初始 dp[0] = 1。dp[j] |= dp[j - bar 重量]。 表示如果j-bar重量那個dp為1，那dp[j] 肯定能為1。

這邊用法1 解

代碼:  

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

int len[25];
int main()
{
    //freopen("out.txt", "w", stdout);
    int t, n, p;
    cin >> t;
    while(t--){
        cin >> n >> p;
        for(int i = 0; i < p; ++i) cin >> len[i];
        bool ok = 0;
        for(int i = 0; i < (1<<p); ++i){
            int sum = 0;
            for(int j = 0; j < p; ++j){
                if(i & (1<<j)) sum += len[j];
            }
            if(sum == n){
                ok = 1; break;
            }
        }
        puts(ok ? "YES": "NO");
    }
    return 0;
}