admin 管理员组

文章数量: 1184232

九度OJ 1114：神奇的口袋 （DFS、DP）

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：948

解决：554

题目描述：

有一个神奇的口袋，总的容积是40，用这个口袋可以变出一些物品，这些物品的总体积必须是40。John现在有n个想要得到的物品，每个物品的体积分别是a1，a2……an。John可以从这些物品中选择一些，如果选出的物体的总体积是40，那么利用这个神奇的口袋，John就可以得到这些物品。现在的问题是，John有多少种不同的选择物品的方式。

输入：

输入的第一行是正整数n (1 <= n <= 20)，表示不同的物品的数目。接下来的n行，每行有一个1到40之间的正整数，分别给出a1，a2……an的值。

输出：

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

样例输入： 
3
20
20
20
样例输出： 
3
来源：
2007年北京大学计算机研究生机试真题

思路：

DFS可解，复杂度O(n)，因此n比较大的时候复杂度高。

另一种方法是类似01背包的动态规划，当解空间不大时比较适合。

本代码为DFS。


代码：

#include <stdio.h>
#include <stdlib.h>#define N 20
#define SUM 40int sum;
int count = 0;
int a[N];int cmp(const void *a, const void *b)
{return *(int *)a - *(int *)b;
}void choose(int sum, int n)
{if (sum == SUM){count ++;return ;}if (n == 0)return ;if (sum + a[n-1] <= SUM)choose(sum + a[n-1], n-1);choose(sum , n-1);
}int main(void)
{int n, i;while (scanf("%d", &n) != EOF){for(i=0; i<n; i++)scanf("%d", &a[i]);qsort(a, n, sizeof(a[0]), cmp);count = 0;choose(0, n);printf("%d\n", count);}return 0;
}
/**************************************************************Problem: 1114User: liangrx06Language: CResult: AcceptedTime:0 msMemory:912 kb
****************************************************************/


本文标签： 九度OJ 1114神奇的口袋 （DFSDP）

版权声明：本文标题：九度OJ 1114：神奇的口袋 （DFS、DP） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.roclinux.cn/b/1693761776a241313.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。