时间限制 1000 ms 内存限制 64 MB
题目描述
李老师正准备暑假旅行，他有一个容量为L的行李箱和n个物品（n不超过20），每个物品都有自己的体积，物品可以放入行李箱，但行李箱中物品的总体积不能超过行李箱容量，李老师现在想知道他有多少种携带物品的方案（一个物品都不带也算一种方案）
输入数据
第一行为两个正整数n和L，分别代表物品总数和行李箱容量，n<=20，L<=1e9 接下来一行为n个正整数vi，代表第i个物品的体积，vi<=1e8
输出数据
方案数
样例输入
3 10 2 4 5
样例输出
7
#include <iostream> #include <algorithm> #include <cmath> using namespace std; int ans = 0; int n; int L; int a[20]; int tmp = 0; void fun(int tag, int total) { if (tag == n) { ans++; //cout << "total = " << total << endl; return; } int tmptag = tag + 1; int tmptotal = total + a[tag]; if (total <= L) { fun(tmptag, total); } if (tmptotal <= L) { fun(tmptag, tmptotal); } } int main() { cin >> n >> L; for (int i = 0; i < n; i++) { cin >> a[i]; } fun(0, 0); cout << ans << endl; return 0; }