神奇的口袋

题目描述

有一个神奇的口袋，总的容积是 40，用这个口袋可以变出一些物品，这些物品的总体积必须是 40。

John 现在有 n 个想要得到的物品，每个物品的体积分别是 a_1,a_2……a_n。

John 可以从这些物品中选择一些，如果选出的物体的总体积是 40，那么利用这个神奇的口袋，John 就可以得到这些物品。

现在的问题是，John 有多少种不同的选择物品的方式。

输入格式

输入的第一行是正整数 n，表示不同的物品的数目。

接下来的 n 行，每行有一个 1 到 40 之间的正整数，分别给出 a_1,a_2……a_n 的值。

输出格式

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

题目分析

此题为01背包的变种问题，01背包求的是在不超过背包容量下最大能装的价值，而此题是求恰好满足容量是j(40)的情况下，装物品的的方案数。

状态定义: f[i][j]表示考虑前i个物品总重量恰好等于j的方案数

集合划分:根据第i个物品选或者不选将集合划分为两部分

状态计算: f[i][j] = f[i - 1][j] + f[i - 1][j - w[i]]

代码

#include <iostream>

using namespace std;
const int N = 50;

int f[N][N];

int n;
int a[N];

int main()
{
  cin >> n;
  for(int i = 1;i <= n; i++)cin >> a[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( a[i] <= j )f[i][j] += f[i - 1][j - a[i]];
    }
  
  cout << f[n][40] << endl;
  return 0;
}