P10483 小猫爬山

1.

#include<bits/stdc++.h>
using namespace std;
//一个记录小猫的重量，sum记录当前小猫的重量之和
int n, w, a[3000],sum[3000],ans;
bool cmp(int a,int b) {return a > b;
}
//x表示小猫当前的编号，cnt表示缆车的数量
void dfs(int x,int cnt) {if (cnt >= ans)return;if (x == n + 1)ans = cnt;ans = min(ans, cnt);for (int i = 1; i <= cnt; i++) {if (a[x]+sum[i]<=w) {sum[i] += a[x];dfs(x+1,cnt);sum[i] -= a[x];}//超出w,开启下一辆车sum[cnt+1] = a[x];dfs(x + 1, cnt+1);sum[cnt+1] = 0;}
}
int main() {cin >> n >> w;ans = n;for (int i = 1; i <= n; i++) {cin >> a[i];}sort(a+1,a+n+1,cmp);dfs(1,1);cout << ans;return 0;
}

2.

#include<bits/stdc++.h>
using namespace std;
int n,w,ans,sum[2000],p[2000];
bool cmp(int a,int b){return a>b;
}
void dfs(int u,int k){if(k>=ans) return ;//剪枝if(u==n+1) ans=k;//记录答案for(int i=1;i<=k;i++){if(sum[i]+p[u]<=w){sum[i]+=p[u];dfs(u+1,k);sum[i]-=p[u];}}sum[k+1]=p[u];dfs(u+1,k+1);//多使用一个缆车sum[k+1]=0;
}
int main(){cin>>n>>w;ans=n;for(int i=1;i<=n;i++) cin>>p[i];//sort(p+1,p+1+n,cmp);//可以不使用排序dfs(1,1);cout<<ans;return 0;
}