小猫爬山(逐层优化版)

版本1

最简单的想法(16/17)

一只一只安排 不断计算开辟新的小车花费
计算到花费比目前得到的最小花费大的时候剪掉

Code

#include<bits/stdc++.h>
using namespace std;
const int N=20;
int sum[N],n,m,w[N],ans=1e6;
//dfs(u,k) 当前为u只猫 所花费为k元
void dfs(int u,int k)
{
    if(u>n)
    {
        ans=min(ans,k);
        return;
    }
    if(k>=ans) return;
    for(int i=1;i<=k;i++)
    {
        if(sum[i]+w[u]<=m)
        {
        sum[i]+=w[u];
        dfs(u+1,k);
        sum[i]-=w[u];
        }
    }
    sum[k+1]=w[u];
    dfs(u+1,k+1);
    sum[k+1]-=w[u];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>w[i];
    dfs(1,1);
    cout<<ans;
    return 0;
}

版本2(AC) 豆包提示优化思路

对小猫的体重进行降序排序
为什么:先安排一些比较小的进去后面大的就坐不上了,导致一定的空间浪费 (详见参考1)

#include<bits/stdc++.h>
using namespace std;
const int N=20;
int sum[N],n,m,w[N],ans=1e6;
//dfs(u,k) 当前为u只猫 所花费为k元
bool cmp(int a,int b)
{
    return a>b;
}
void dfs(int u,int k)
{
    if(u>n)
    {
        ans=min(ans,k);
        return;
    }
    if(k>=ans) return;
    for(int i=1;i<=k;i++)
    {
        if(sum[i]+w[u]<=m)
        {
        sum[i]+=w[u];
        dfs(u+1,k);
        sum[i]-=w[u];
        }
    }
    sum[k+1]=w[u];
    dfs(u+1,k+1);
    sum[k+1]-=w[u];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>w[i];
    sort(w+1,w+1+n,cmp);
    dfs(1,1);
    cout<<ans;
    return 0;
}

参考一

示例说明

假设现有 4 只小猫，重量分别为 2、3、7、8，缆车最大承重量 W = 10。

先安排小重量小猫的情况

1. 顺序：按重量从小到大（2 → 3 → 7 → 8）。
2. 分配过程：
3. 第一辆缆车：放入 2 和 3，剩余空间 10 - (2 + 3) = 5。
4. 第二辆缆车：放入 7，剩余空间 10 - 7 = 3。
5. 第三辆缆车：放入 8（无法放入前两辆）。
6. 结果：共需 3 辆缆车。

先安排大重量小猫的情况

1. 顺序：按重量从大到小（8 → 7 → 3 → 2）。
2. 分配过程：
3. 第一辆缆车：放入 8，剩余空间 10 - 8 = 2。
4. 第二辆缆车：放入 7，剩余空间 10 - 7 = 3。
5. 第一辆缆车：放入 2（剩余空间 2 刚好容纳）。
6. 第二辆缆车：放入 3（剩余空间 3 刚好容纳）。
7. 结果：共需 2 辆缆车。

原理分析

1. 小重量优先的问题：
2. 小重量小猫对缆车空间的占用不充分，可能导致后续大重量小猫无法被分配到同一辆缆车。

3. 例如，第一辆缆车剩余空间 5 无法容纳 7 和 8，必须新增缆车。

4. 大重量优先的优势：

5. 大重量小猫优先填满缆车，减少空间浪费。
6. 剩余空间可被后续小重量小猫充分利用。

总结

• 降序排序能避免小重量小猫占用过多零散空间，从而减少总缆车数量。
• 贪心策略通过优先处理大重量小猫，更快接近最优解，减少递归分支。