JCYZOJ2 小猫爬山

题目描述 
Freda 和 rainbow 饲养了 N 只小猫,这天,小猫们要去爬山。经历了千辛万 苦,小猫们终于爬上了山顶,但是疲倦的它们再也不想徒步走下山了(呜咕>_<)。 Freda 和 rainbow 只好花钱让它们坐索道下山。索道上的缆车最大承重量为 W,而 N 只小猫的重量分别是 C1、C2……CN。当然,每辆缆车上的小猫的重 量之和不能超过 W。每租用一辆缆车,Freda 和 rainbow 就要付 1 美元,所以他 们想知道,最少需要付多少美元才能把这 N 只小猫都运送下山?
输入格式
第一行包含两个用空格隔开的整数,N 和 W。 接下来 N 行每行一个整数,其中第 i+1 行的整数表示第 i 只小猫的重量 Ci。
输出格式
输出一个整数,最少需要多少美元,也就是最少需要多少辆缆车。
样例输入
5 1996 1 2 1994 12 29
样例输出
2
数据范围与约定 
对于 100%的数据,1<=N<=18,1<=Ci <=W<=10^8。

LYD的大水题。。。。只有18只猫。。。。直接暴力

#include<iostream>
#include<cstdio>
#include<algorithm> 
#include<cstring> 
using namespace std;
int a[20],f[20],n,m,ID,i; 

bool cmp(int a,int b) {return a>b;}

bool dfs(int x)
{
	if(x>n) return 1;
	for(int i=1;i<=x&&i<=ID;i++)
		if(f[i]+a[x]<=m)
		{
			f[i]+=a[x];
			if(dfs(x+1)) return 1;
			f[i]-=a[x];
		}
	return 0; 
}

int main()
{
	cin>>n>>m;
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1,cmp);
	for(ID=1;ID<=n;ID++)
	{
		memset(f,0,sizeof(f));
		if(dfs(1)) break;
	}
	cout<<ID<<endl;
	return 0;
}

 

此条目发表在DFS, DP, JCYZOJ, 搜索分类目录。将固定链接加入收藏夹。