欢迎访问==> 【考研OR保研】机试题
题目描述
有一个神奇的口袋,总的容积是 $40$,用这个口袋可以变出一些物品,这些物品的总体积必须是 $40$。
John 现在有 $n$ 个想要得到的物品,每个物品的体积分别是 $a_1,a_2……a_n$。
John 可以从这些物品中选择一些,如果选出的物体的总体积是 $40$,那么利用这个神奇的口袋,John 就可以得到这些物品。
现在的问题是,John 有多少种不同的选择物品的方式。
输入格式
输入的第一行是正整数 $n$,表示不同的物品的数目。
接下来的 $n$ 行,每行有一个 $1$ 到 $40$ 之间的正整数,分别给出 $a_1,a_2……a_n$ 的值。
输出格式
输出不同的选择物品的方式的数目。
数据范围
$1 \\le n \\le 20$,
$1 \\le a_i \\le 40$
输入样例:
3
20
20
20
输出样例:
3
C++ 代码
01背包问题的变种,具体请参考01背包问题
#include <bits/stdc++.h>
using namespace std;
const int N = 50;
/*
状态定义:f[i][j]表示考虑前i个物品总重量恰好等于j的方案数
集合划分:根据第i个物品选或者不选将集合划分为两部分
状态计算:f[i][j] = f[i - 1][j] + f[i - 1][j - w[i]]
*/
int f[N][N];
int n, w[N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++) cin >> w[i];
f[0][0] = 1; //初始化
for(int i = 1; i <= n; i ++)
{
for(int j = 0; j <= 40; j ++)
{
f[i][j] = f[i - 1][j];
if(j >= w[i]) f[i][j] += f[i - 1][j - w[i]];
}
}
cout << f[n][40] << endl;
return 0;
}