时间限制 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 <stdio.h>
#include<math.h>
#include<iomanip>
#include "stdlib.h"
#include <iostream>
using namespace std;
void iteration(int n, int N, int v, int V, int *count, int a[]);
int main()
{
int L, n;
int *a;
cin >> n >> L;
a = (int *)malloc(sizeof(int) * n); // 分配
for (int i = 0; i<n; i++)
{
cin >> a[i]; // 键盘输入 n 个数
}
int c = 0;
int *count = &c;
iteration(0, 0, n, L, count, a);
cout << *count << endl;
}
void iteration(int n, int l, int N, int L, int *count, int a[])
{
if ((n > N)||(l>L))
return;
if (l + a[n] <= L)
{
if (n == N)
{
*count += 1;
return;
}
else
{
iteration(n + 1, l, N, L, count, a);
l = l + a[n];
iteration(n + 1, l, N, L, count, a);
}
}
else
{
iteration(n + 1, l, N, L, count, a);
}
}
