简答题 偏难
#7094

忍者道具 忍者道具有很多种,苦无,飞镖,震爆弹。L君热衷于收集忍者道具,现在他有N个道具,每个道具的重量分别是C 1 、C 2 …C N 。现在他想把这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">#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><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>
这道题暂未补解析。