专做耐克阿迪鞋网站,wordpress批量修改图片标题,知名企业,北京网站排名题目描述
现有 n n n 个砝码#xff0c;重量分别为 a 1 , a 2 , … , a n a_1, a_2, \ldots,a_n a1,a2,…,an #xff0c;在去掉 m m m 个砝码后#xff0c;问最多能称量出多少不同的重量#xff08;不包括 0 0 0 #xff09;。
输入格式
第一行为有两个整数…题目描述
现有 n n n 个砝码重量分别为 a 1 , a 2 , … , a n a_1, a_2, \ldots,a_n a1,a2,…,an 在去掉 m m m 个砝码后问最多能称量出多少不同的重量不包括 0 0 0 。
输入格式
第一行为有两个整数 n n n 和 m m m 用空格分隔。 第二行有 n n n 个正整数 a i a_i ai 表示每个砝码的重量。
输出格式
输出一行一个整数表示最多能称量出的重量的数量。
样例
样例输入1
3 1
1 2 2样例输出1
3样例解释1 在去掉一个重量为 2 2 2 的砝码后能称量出 1 , 2 , 3 1, 2, 3 1,2,3 共 3 3 3 种重量。
数据范围
对于 20 % 20\% 20% 的数据 m 0 m 0 m0。 对于 50 % 50\% 50% 的数据 m ≤ 1 , n ≤ 10 m \le 1,n\le 10 m≤1,n≤10。 对于 100 % 100\% 100% 的数据 n ≤ 20 , m ≤ 4 , m n , a i ≤ 100 n \le 20, m \le 4,m n,a_i \le 100 n≤20,m≤4,mn,ai≤100。
题解
对于 20 % 20\% 20% 的数据去掉 0 0 0 个砝码就是一个 01背包 问题。
对于 50 % 50\% 50% 的数据枚举每个数是否选择判断去掉个数后做 01背包。
对于 100 % 100\% 100% 的数据对上面的搜索进行剪枝如果去掉个数大于 m m m返回。也可以枚举去掉的砝码会快一些。
#includebits/stdc.h
using namespace std;
int n, m;
int a[23];
bool f[23];
int dp[2010];
int ans 0;
void solve(){//01 背包memset(dp, 0, sizeof(dp));dp[0] 1;int s 0;//01 背包每次最多更新到多少for(int i 1; i n; i){if(f[i]){continue;}s a[i];for(int j s; j a[i]; -- j){if(dp[j - a[i]]){dp[j] 1;}}}//统计个数int sum 0;for(int i s; i 1; -- i){if(dp[i]){ sum;}}ans max(ans, sum);
}
//搜索
void dfs(int x, int y){if(y m){solve();return;}for(int i x 1; i n; i){f[i] 1;dfs(i, y 1);f[i] 0;}
}
