简答题
偏难
#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 <iostream>
using namespace std;
const int MAXN = 18;
int used[MAXN];
int W;
int m, n, ans = (1 << 30);
int item[MAXN];
int bag[MAXN];
void dfs(int x, int sum) {
if (sum >= ans) return;
if (x == n) {
ans = min(ans, sum);
return;
}
for (int i = 0; i < sum; ++i) {
if (bag[i] >= 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 >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> item[i];
bag[i] = m;
}
dfs (0, 1);
cout << ans << endl;
return 0;
}</pre><p><br/></p><pre class="brush:cpp;toolbar:false">//解法2 深搜
#include <bits/stdc++.h>
using namespace std;
int n,w,ans=20;
int a[20],bag[20];
void dfs(int x,int sum){//放第x个物品,已使用sum个包
if(sum>=ans) return;//背包数量不够
if(x>n) {ans=min(ans,sum);return;}//所有物品已放完
for(int i=1;i<=sum;i++){//放入现有背包
if(bag[i]>=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>>n>>w;
for(int i=1;i<=n;i++) {
cin>>a[i];
bag[i]=w;//初始化n个背包的开始可用容量
}
dfs(1,1);
cout<<ans<<endl;
return 0;
}</pre>
这道题暂未补解析。