dfs 7pts 求大佬指教,可得2关注
查看原帖
dfs 7pts 求大佬指教,可得2关注
1187511
daijinxiang楼主2024/8/16 21:17

MY code:

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,ans=20,cnt,w;
int c[200],g[200];
bool cmp(int x,int y) {
	return x>y;
}
void dfs(int cnt,int k) {
	if(cnt>=ans) return ;
	if(k>n) {
		ans=cnt;
		return ;
	}
	for(int i=1; i<=cnt; i++) {
		if(g[i]+c[k]<=w) {
			g[i]+=c[k];
			dfs(cnt,k+1);
			g[i]-=c[k];
		}
	}
	g[cnt+1]=c[k];
	dfs(cnt+1,k+1);
	g[cnt-1]=0;
}
int main() {
	cin>>n>>w;
	for(int i=1; i<=n; i++) cin>>c[i];
	sort(c+1,c+1+n,cmp);
	dfs(1,1);
	cout<<ans<<endl;
	return 0;
}
2024/8/16 21:17
加载中...