L2-1特殊的沉重球

NC205549. L2-1特殊的沉重球

描述

StarrySky 在初入精灵宝可梦世界探索的时候，偶遇了一只野生的卡比兽，可是，StarrySky 扔完了手上的精灵球都不能捕捉成功，只好狠下心来让自己当时首发的路卡利欧使用出波导弹打死了它。

后来，StarrySky 发现了一个特殊的精灵球，叫作沉重球，它的特性是：当捕捉体重较大的宝可梦时，会增加成功率。

当发现沉重球之后，StarrySky 突然好后悔，如果在当时用沉重球捕捉卡比兽的话，或许局面就会完全不一样了。

抬头望天，晴空万里，一辆辆缆车在不远处滑过，上面的训练家以及他的宝可梦在友好的玩耍嬉闹，欣赏风景。

StarrySky 突发奇想，如果沉重球再特殊一点呢？

如果一个沉重球的最大承重为 w，只要放入其中的宝可梦的总重量不超过 w，不论几只宝可梦都可以放进去，然后再用缆绳挂起这个沉重球滑行，那个感觉似乎十分不错。

现在 StarrySky 手中有 n 只宝可梦，宝可梦的体重为 $c_i$ ，问至少需要多少个特殊的沉重球才能装下这 n 只宝可梦？

输入描述

第一行输入两个正整数 n, w，表示宝可梦的数量以及每个特殊沉重球的最大承重。

第二行输入 n 个正整数 $c_1, c_2, ..., c_n$ ，依次表示 n 只宝可梦的重量。

输出描述

一行一个正整数，表示能够装下这 n 只宝可梦的最少的特殊沉重球的数量。

示例1

输入:

5 1996
1 2 1994 12 29

输出:

说明:

第一个沉重球放入第 1, 2, 4, 5 只宝可梦，第二个沉重球放入第 3 只宝可梦，这种方法只需要 2 个沉重球。
放法不唯一，比如，也可以将第 2 只宝可梦放入第二个沉重球，但无论如何，该样例的最少所需的沉重球数量为两个。

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 2ms, 内存消耗: 504K, 提交时间: 2020-05-03 15:25:08

#include<bits/stdc++.h>
using namespace std;
int cmp(int a,int b)
{
	return a>b;
}
int n,a[22],p[22],res=0x3f3f3f3f,w;
void dfs(int x,int cnt)
{
	if(cnt>=res)	return ;
	if(x==n+1)
	{
		res=min(res,cnt);
		return ;
	}
	for(int i=1;i<=cnt;i++)
	{
		if(p[i]+a[x]<=w)
		{
			p[i]+=a[x];
			dfs(x+1,cnt);
			p[i]-=a[x];
		}
	}
	p[cnt+1]=a[x];
	dfs(x+1,cnt+1);
	p[cnt+1]=0;
}
int main()
{
	cin>>n>>w;
	for(int i=1;i<=n;i++)	cin>>a[i];
	sort(a+1,a+n+1,cmp);
	dfs(1,0); 
	cout<<res<<endl;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 5ms, 内存消耗: 588K, 提交时间: 2020-05-04 12:13:09

#include<bits/stdc++.h>
using namespace std;
int n,w,a[50],ans=1234567,v[50],cnt=0;
void dfs(int k,int cnt){
	if(cnt>=ans)return ;
	if(k>=n){
		ans=min(ans,cnt);
		return ;
	}
	for(int i=0;i<=cnt;i++){
		if(v[i]+a[k]<=w){
			v[i]+=a[k];
			dfs(k+1,cnt);
			v[i]-=a[k];
		}
	}
	v[cnt+1]+=a[k];
	dfs(k+1,cnt+1);
	v[cnt+1]-=a[k];
}
int main() {
	cin>>n>>w;
	for(int i=0; i<n; i++)cin>>a[i];
	sort(a,a+n,greater<int>());
	dfs(0,0);
	cout<<ans+1;
	return 0;
}