題目：
題目描述
現有n個砝碼，重量分別為a1，a2，a3，……，an，在去掉m個砝碼后，問最多能稱量出多少不同的重量（不包括0）。
輸入輸出格式
輸入格式：
?
輸入文件weight.in的第1行為有兩個整數n和m，用空格分隔
第2行有n個正整數a1，a2，a3，……，an，表示每個砝碼的重量。
?
輸出格式：
?
輸出文件weight.out僅包括1個整數，為最多能稱量出的重量。
?
輸入輸出樣例
輸入樣例#1：
3 1 1 2 2
輸出樣例#1：
3
說明
【樣例說明】
在去掉一個重量為2的砝碼后，能稱量出1，2，3共3種重量。
【數據規模】
對于20%的數據，m=0；
對于50%的數據，m≤1；
對于50%的數據，n≤10；
對于100%的數據，n≤20，m≤4，m＜n，ai≤100。
?
#include <iostream> #include <cstring> using namespace std; int n, m, MAX = 0, answer = 0; int Weight[21]; int F[20001]; bool judge[21]; int Find()//判斷每一種重量是否存在，因為所產生的所有的值只可能是1~maxx之間的數 {int total = 0;memset(F, 0, sizeof(F));F[0] = 1;for (int i = 1; i <= n; i++){if (!judge[i]){for (int j = MAX; j >= Weight[i]; j--){F[j] += F[j - Weight[i]];}}}for (int i = 1; i <= MAX; i++){if (F[i]){total++;}}answer = max(answer, total); } void Search(int counts, int pos) {if (counts == m + 1){Find();}else{if (pos > n){return ;//從1~n來一遍}judge[pos] = true;Search(counts + 1, pos + 1);//某一個數字在組合的過程中只有兩種可能，一種是選，一種是不選，所以會出現兩種情況，故搜兩次
judge[pos] = false;Search(counts, pos + 1);} } int main() {cin >> n >> m;for (int i = 1; i <= n; i++){cin >> Weight[i];MAX += Weight[i];//計算出總重量}if (m == 0){Find();}Search(1, 1);cout << answer << endl; }
?
