首页 > 代码库 > 砝码称重 洛谷 1441

砝码称重 洛谷 1441

题目:

题目描述

现有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; }

 

砝码称重 洛谷 1441