首页 > 试题广场 >

神奇的口袋

[编程题]神奇的口袋
  • 热度指数：18636 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
有一个神奇的口袋，总的容积是40，用这个口袋可以变出一些物品，这些物品的总体积必须是40。John现在有n个想要得到的物品，每个物品的体积分别是a1，a2……an。John可以从这些物品中选择一些，如果选出的物体的总体积是40，那么利用这个神奇的口袋，John就可以得到这些物品。现在的问题是，John有多少种不同的选择物品的方式。

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


输出描述:
输出不同的选择物品的方式的数目。
示例1

输入

3
20
20
20

输出

3
算法知识视频讲解
开通博客
头像 健康快乐最重要
发表于 2020-03-26 15:55:34
dfs可以做 #include<iostream> using namespace std; const int maxn=21; int a[maxn]; int vis[maxn],res,n; void dfs(int now,int j){ for(int i=j;i& 展开全文
去ta的博客 赞 (13) 回复(7) 收起
头像 Wait！
发表于 2022-03-03 13:57:57
此题应该选择递归法，且递归思路为：n个物品选择体积和为40的情况数目= 前n-1个物品选择体积和为40的情况数目+前n-1个物品选择体积和为 ‘40-第n个物品体积’ 的情况数目 以此递推。 当最后递推到只剩一个物品时，若要求从这一个物品中选择体积和为0的情况，即不选择，则返回1（因为此处不选择也是 展开全文
去ta的博客 赞 (11) 回复(0) 收起
头像 普罗列塔丽亚
发表于 2022-02-11 16:27:49
【01背包问题】从后往前滚动数组 【要求凑整数】边界值：[0][0]=1，0枚硬币凑0面值、算一种方案；[0][j]=0 【统计方案数】转移方程：a+b #include<iostream> #include<climits> using n 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 Huster水仙
发表于 2023-01-28 21:01:46
DFS 采用void型 不论当前是否查找成功，都要继续递归，不可直接终止，遍历所有可能 #include<iostream> #include<algorithm> #include<cstring> using namespace std; int sum; 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 Coming680
发表于 2022-02-09 22:51:57
#include<iostream> #include<algorithm> using namespace std; int cnt = 0; void dfs(int v[],int n,int total,int pos){ if(total == 40){ 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 Coder_Karl
发表于 2022-03-15 14:02:46
#include <stdio.h> #include <malloc.h> #define SUM 40 short find(short p[], short n, short&n 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 KoukiAlpha
发表于 2023-01-12 22:45:55
#include <iostream> using namespace std; int v[21]; int judge(int index,int remain){ if(remain == 0) return 1; //成功 if(index <= 0) 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 想潜水的土拨鼠已run
发表于 2024-01-24 23:03:54
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int MAX = 20; int stuff[MAX]; int sum=0 ; 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 XwwwwL
发表于 2023-03-01 16:56:41
//题目要求搜寻所有解，而不是是否可以，所以DFS时，不能找到一个解，就全部退出，而是应该遍历所有、 #include <iostream> using namespace std; int n; int box[25]; bool visit[25]; int curside = 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 TradingYesterday
发表于 2024-03-06 09:51:20
写题思路 ： 这题 两种方法 动规 和 回溯 都能做动规的话 看题目问 有多少种方式 这种一眼组合数的dp板子 核心状态转移方程：dp[j] += dp[j - goods[i]];然后dp[0]初始化为1 然后一维滚动数组 遍历背包时 要从末尾开始 这个地方建议多看看 carl哥的归纳总结 还是很 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

动态规划 递归
难度：
83条回答 15287浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号