Final Dash


每日进步

题目

P2744[USACO5.3]量取牛奶

知识点：迭代加深，完全背包

复习1:迭代加深

深搜

从根节点一直往下走，直到叶子搜索完再返回上一层。

image.png

深搜的缺点很明显：如果答案状态所在的结点深度不大，那么搜到这个结点之前，对非常深的状态进行的搜索都是徒劳的。

image.png

广搜

从根节点开始，一层层往下搜索，直到最后才能走到叶子节点。

image.png

广搜的问题也很明显。如果目标状态的深度稍微深一些，用于保存状态的队列所需的空间就会指数级增长。

两者结合？

深搜广搜都有自己的缺点。迭代加深(iterative deepening,简称ID)则结合两者的优点，用深搜模拟广搜。为了避免过大的空间需求，必须使用深搜。为了避免搜索无用且过深的搜索树，必须按广搜的模式控制搜索深度。

具体实现

深搜之前，我们设定一个限定的深度，要求深搜不得超过这个深度。每一次深搜，我们检查当前所处的深度。如果达到限定的深度，立刻返回。一次完整的深搜完成，如果没有找到答案，增加限定的深度，继续ID。

image.png

复习2:完全背包

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

因为同种物品可以多次选取，那么第i种物品最多可以选取V/C[i]件价值不变的物品，然后就转化为01背包问题。

如果把第i种物品拆成体积为C[i]×2k价值W[i]×2k的物品，其中满足C[i]×2k≤V。即设F[i][j]表示出在前i种物品中选取若干件物品放入容量为j的背包所得的最大价值。那么对于第i种物品的出现，我们对第i种物品放不放入背包进行决策。

如果不放那么F[i][j]=F[i-1][j]；如果确定放，背包中应该出现至少一件第i种物品，所以F[i][j]种至少应该出现一件第i种物品,即F[i][j]=F[i][j-C[i]]+W[i]。为什么会是F[i][j-C[i]]+W[i]？因为F[i][j-C[i]]里面可能有第i种物品，也可能没有第i种物品。我们要确保F[i][j]至少有一件第i件物品，所以要预留C[i]的空间来存放一件第i种物品。

实现

状态方程：$ F[i][j]= Max \begin{cases}
F[i-1][j]\
F[i][j-C[i]]+W[i] , j \ge C[i]
\end{cases}$

一维数组上区别0-1背包和完全背包差别就在循环顺序上，0-1背包必须逆序，因为这样保证了不会重复选择已经选择的物品，而完全背包是顺序，顺序会覆盖以前的状态，所以存在选择多次的情况，也符合完全背包的题意。

思路

整体思路是先用迭代加深搜索求出瓶子规格的一种组合，例如1个瓶子的所有组合，2个瓶子的所有组合，3个瓶子时候的组合。由于要求选择较小“集合”，所以应当先将瓶子按规格排序。

当得出某个组合后，瓶子可以无限量使用，所有转化为完全背包：用可以反复使用的数字拼出背包容量。

代码

const int N=10000+10;
int p,q,a[N],k,use[N];
inline void print(){
    cout<<k<<" ";
    for(int i=1; i<=k; i++) cout<<a[use[i]]<<" ";
    cout<<endl;
    exit(0);
}
void dp(){ //完全背包，判断取k个瓶子能否取到体积为q的情况

    int f[2*N]; memset(f,0,sizeof(f)); f[0]=1; //f[i]:体积为i时能否取到
    for(int i=1; i<=k; i++) //初始化
        for(int j=1; j<=q/a[use[i]]; j++)
            f[j*a[use[i]]]=1; //倍数都可取
    for(int i=1; i<=k; i++)
        for(int j=a[use[i]]; j<=q; j++)
            f[j]=f[j]||f[j-a[use[i]]]; //或
    if(f[q]) print(); //一取到就输出（字典序最小
}
void dfs(int x){
    for(int i=use[x-1]+1; i<=p-k+x; i++){ //下一次递归就是上次取到瓶子的下一个开始多取一次
        use[x]=i; //use[i]:记录第i个桶时桶的编号
        if(x==k) dp(); //直到去到k个瓶子为止=>完全背包
        else dfs(x+1);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>q>>p;
    for(int i=1; i<=p; i++) cin>>a[i];
    sort(a+1,a+p+1); //保证最先找到的是最小组合
    for(k=1; k<=p; k++) dfs(1); //依次枚举k个瓶子的所有组合
    return 0;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议


 上一页