[人工智能]算法笔记【回溯算法+搜索与剪枝 +二分类】切蛋糕

1020. 切蛋糕
      时间限制 1000 ms
      内存限制 128 MB
      题目描述
      　　Facer今天买了n块蛋糕，不料被信息组中球球等好吃懒做的家伙发现了，没办法，只好浪费一点来填他们的嘴巴。他答应给每个人留一口，然后量了量每个人口的大小。Facer有把刀，可以切蛋糕，但他不能把两块蛋糕拼起来，但是他又不会给任何人两块蛋糕。现在问你，facer怎样切蛋糕，才能满足最多的人。（facer的刀很强，切的时候不会浪费蛋糕）。

输入数据
第一行 n,facer 有 n 个蛋糕。接下来 n 行，每行表示一个蛋糕的大小。再一行一个数 m， 为信息组的人数，然后 m 行，每行一个数，为一个人嘴的大小。 (1≤n≤50,1≤m≤1024)
输出数据
一行 ，facer 最多可以填多少张嘴巴。
样例输入
4
30
40
50
25
10
15
16
17
18
19
20
21
25
24
30
样例输出
7

其实，我还不太懂，先占个坑吧，之后再多刷几道回溯的题再说

#include<iostream>
#include<algorithm>
#define bug cout<<"no error!";
using namespace std;
int mouth[10000],cake[10000],c[10000],pre[10000],waste,all,n,m,l,r,mid,ans,maxn;//变量的意思（依次）
//嘴的大小、蛋糕的大小、蛋糕大小副本、前缀和、浪费值、蛋糕总体积 、蛋糕个数、嘴的个数、二分左边界、右边界
//二分的中点、答案、最大的蛋糕的体积
int dfs(int num,int same_start)//num表示剩下的要满足的人数，同时也巧妙的表示了人嘴的编号
//same_start未剪枝时都可以当做1，而在进行剪枝时的用处详见上文
{
    if(num==0) return 1;//能够分配完所有的人，那么返回1
    if(all-waste<pre[mid]) return 0;//剪枝优化1，详见上文
    for(int i=same_start;i<=n;i++)
    {
        if(c[i]>=mouth[num])
        {
            c[i]-=mouth[num];//如果能满足这个人，那么就让他吃掉，进行试探
            if(c[i]<mouth[1]) waste+=c[i];//如果连口最小的人都满足不了，
            //那么只能浪费,于是增加浪费值，便于上面的剪枝
            if(mouth[num]==mouth[num-1])//剪枝优化2，详见上文
            {
                if(dfs(num-1,i)) return 1;
            }
            else if(dfs(num-1,1)) return 1;
            if(c[i]<mouth[1]) waste-=c[i];//回溯
            c[i]+=mouth[num];//回溯
        }
    }
    return 0;//如果是可以满足的，那么上面会返回的，否则就是不可以满足，返回0
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>cake[i];
        all+=cake[i];//记录蛋糕总量，用于剪枝
        if(cake[i]>maxn) maxn=cake[i];//记录最大的蛋糕大小，后面有用
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    cin>>mouth[i];
    sort(mouth+1,mouth+m+1);//贪心：将每个人按嘴的大小排序
    while(maxn<mouth[m]) m--;//从嘴最大的人开始，如果嘴比最大的蛋糕还大，那么一定无法满足
    //因为无法将两块蛋糕拼起来给人
    for(int i=1;i<=m;i++)
    pre[i]=pre[i-1]+mouth[i];//记录前缀和，用于剪枝
    l=0;r=m;//规定好二分查找左右边界
    while(l<=r)
    {
        waste=0;//浪费值初始为0
        mid=(l+r)/2;
        for(int i=1;i<=n;i++) c[i]=cake[i];//如果在搜索中用cake数组的话，可能在没有回溯前就返回了，
        //那样cake值会变，影响下一轮搜索，所以赋值到c数组中，使用c数组代替，就像是常说的副本一样
        if(dfs(mid,1))
        {
            ans=mid;//如果这个猜测能完成，那么就要记录下答案，不停覆盖，直到最后找到
            l=mid+1;
        }
        else r=mid-1;//注意：这里千万不要写成r=mid，
        //因为当l=r时，mid=l=r，如果r=mid，那么就会陷入死循环，可以自己模拟一下，l会永远等于r
        //这种情况不可能r<l，所以会一直循环
        //或者这里写成r=mid，但是while的小括号里必须换一个判定条件：l<r也是可以的
    }
    cout<<ans;
    return 0;
}

这个大佬给了我很多灵感，链接

这个大佬写的很简洁，循序渐进，可以参考 链接2