大力出奇迹----旅行背包

题目描述

李老师正准备暑假旅行，他有一个容量为L的行李箱和n个物品（n不超过20），每个物品都有自己的体积，物品可以放入行李箱，但行李箱中物品的总体积不能超过行李箱容量，李老师现在想知道他有多少种携带物品的方案（一个物品都不带也算一种方案）

输入数据

第一行为两个正整数n和L，分别代表物品总数和行李箱容量，n<=20，L<=1e9 接下来一行为n个正整数vi，代表第i个物品的体积，vi<=1e8

输出数据

方案数

样例输入

3 10

2 4 5

样例输出

7

思路：

递归的思路，每种物品都有拿或者不拿两种选择，建立一颗完全二叉树

代码：

#include<iostream>#include<math.h>using namespace std;int num = 0;//方案数void Plan(int a[], int id, int volume, int n, int l){if (id == n)//遍历完所有数据{if (volume <= l)//总体积小于等于行李箱的体积num++;return;//结束该函数的调用，否则会继续id+1}Plan(a, id + 1, volume, n, l);//选择不带该物品Plan(a, id + 1, volume + a[id], n, l);//选择带该物品}int main(){int n, l;//物品数和箱子容量cin >> n >> l;int a[20];//物品体积，for (int i = 0; i < n; i++)cin >> a[i];Plan(a, 0, 0, n, l);cout << num << endl;return 0;}

注意事项：

1、没有用类的话，方案数需要定义为全局变量

2、递归结束的条件中需要有return，如果没有的话会继续执行后边的程序，也就是id+1，然而数据已经遍历完毕，因此需要结束上一函数的调用，再返回一层