2755:神奇的口袋

• 查看
• 提交
• 统计
• 提示
• 提问

总时间限制: 

10000ms

内存限制: 

65536kB

描述

有一个神奇的口袋，总的容积是40，用这个口袋可以变出一些物品，这些物品的总体积必须是40。John现在有n个想要得到的物品，每个物品的体积分别是a1，a2……an。John可以从这些物品中选择一些，如果选出的物体的总体积是40，那么利用这个神奇的口袋，John就可以得到这些物品。现在的问题是，John有多少种不同的选择物品的方式。

输入

输入的第一行是正整数n (1 <= n <= 20)，表示不同的物品的数目。接下来的n行，每行有一个1到40之间的正整数，分别给出a1，a2……an的值。

输出

输出不同的选择物品的方式的数目。

样例输入

3
20
20
20

样例输出

3

枚举法

思路简介：

n的范围较小，所以可以考虑用子集枚举

粗略了解子集枚举和位运算可戳如下链接

子集枚举/二进制/位运算 技巧小结 （带例题）C++_Prudento的博客-CSDN博客https://blog.csdn.net/Prudento/article/details/122723928?spm=1001.2014.3001.5502

AC代码如下

#include<bits/stdc++.h>
using namespace std;
#define MAX 21
int a[MAX];
int main(){int n;int cnt = 0;cin>>n;for (int i = 0; i < n; i++)cin >> a[i];for (int s = 0; s < 1 << n; s++) {int sum = 0;for (int i = 0; i < n; i++) {if ((s>>i)&1) {sum += a[i];}}if (sum == 40)cnt++;}cout << cnt;return 0;
}

递归法

思路详见注释

#include<bits/stdc++.h>
using namespace std;
int a[30];
int n;
int Ways(int w, int k) {//从前k种物品中选择一些，凑成体积w的做法数目//先设置边界条件if (w == 0)return 1;//如果体积不够了，那就是什么都不选，也是一种解法if (k <= 0)return 0;//如果物品没了，即不需要选了，即0种方法return Ways(w, k - 1) + Ways(w - a[k],k-1);//对于第k种物品，只有选或者不选两种情况//第k种不选方法数为Ways(w, k - 1)，第k种选即Ways(w - a[k],k-1);
}
int main(){cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];cout<<(Ways(40, n));return 0;
}

动归法

和上述递归法的思路相似，只不过是转成递推动归型，且减少了重复，提高了效率。

#include<bits/stdc++.h>
using namespace std;
int a[30];
int n;
int Ways[41][30];//Ways[i][j]表示从j种物品里凑出体积i的方法数//题目要求的即Ways[40][n]
int main(){cin >> n;memset(Ways,0,sizeof(Ways));for (int i = 1; i <= n; i++) {cin >> a[i];Ways[0][i] = 1;//需要凑的体积为0的时候只有一种方法，即什么物品都不选}Ways[0][0] = 1;//边界条件，什么都没有时，也是一种可能for (int w = 1; w <= 40; w++) {for (int k = 1; k <= n; k++) {Ways[w][k] = Ways[w][k - 1];if (w - a[k] >= 0)Ways[w][k] += Ways[w - a[k]][k - 1];}}cout << Ways[40][n];return 0;
}