首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#7384

忍者道具 忍者道具有很多种,苦无,飞镖,震爆弹。L君热衷于收集忍者道具,现在他有N个道具,每个道具的重量分别是C1、C2…CN。现在他想把这N个道具装到载重量为…

忍者道具

忍者道具有很多种,苦无,飞镖,震爆弹。L君热衷于收集忍者道具,现在他有N个道具,每个道具的重量分别是C1、C2…CN。现在他想把这N个道具装到载重量为W的工具包里,请问他最少需要多少个工具包?

时间限制:1000

内存限制:65536

输入

第一行包含两个用空格隔开的整数,N和W。 接下来N行每行一个整数,其中第i+1行的整数表示第i个道具的重量Ci。

输出

输出一个整数,最少需要多少个工具包。

样例输入

5 1996
1
2
1994
12
29

样例输出

2

提示

对于100%的数据,1<=N<=18,1<=Ci<=W<=10^8。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//解法1 //青少年考级竞赛题库(tiku.scratchor.com)搜集整理,感谢网友提供代码! #include &lt;iostream&gt; using namespace std; const int MAXN = 18; int used[MAXN]; int W; int m, n, ans = (1 &lt;&lt; 30); int item[MAXN]; int bag[MAXN]; void dfs(int x, int sum) { if (sum &gt;= ans) return; if (x == n) { ans = min(ans, sum); return; } for (int i = 0; i &lt; sum; ++i) { if (bag[i] &gt;= item[x]) { bag[i] -= item[x]; dfs(x + 1, sum); bag[i] += item[x]; } } bag[sum] -= item[x]; dfs(x + 1, sum + 1); bag[sum] += item[x]; } int main() { cin &gt;&gt; n &gt;&gt; m; for (int i = 0; i &lt; n; ++i) { cin &gt;&gt; item[i]; bag[i] = m; } dfs (0, 1); cout &lt;&lt; ans &lt;&lt; endl; return 0; }</pre><p><br/></p><pre class="brush:cpp;toolbar:false">//解法2  深搜 #include &lt;bits/stdc++.h&gt;   using namespace std;  int n,w,ans=20; int a[20],bag[20]; void dfs(int x,int sum){//放第x个物品,已使用sum个包 if(sum&gt;=ans) return;//背包数量不够 if(x&gt;n) {ans=min(ans,sum);return;}//所有物品已放完 for(int i=1;i&lt;=sum;i++){//放入现有背包 if(bag[i]&gt;=a[x]){ bag[i]-=a[x]; dfs(x+1,sum); bag[i]+=a[x];//回溯 } } bag[sum+1]-=a[x];//放入新背包 dfs(x+1,sum+1); bag[sum+1]+=a[x];//回溯 } int main() { cin&gt;&gt;n&gt;&gt;w; for(int i=1;i&lt;=n;i++) { cin&gt;&gt;a[i]; bag[i]=w;//初始化n个背包的开始可用容量 } dfs(1,1); cout&lt;&lt;ans&lt;&lt;endl; return 0; }</pre>
这道题暂未补解析。