题解 P2744 【[USACO5.3]量取牛奶Milk Measuring】

· · 题解

S1 一开始看到这道题还是很好确定算法的，妥妥的是dfs+dp。先跑一遍完全背包，vis[i][j]表示体积为j的时候选不选i最优，可以把第一维压掉。如果vis[j-a[i]]选了i，那么vis[j]就不用再选一遍。这样可以确定出来一共选了多少种木桶，之后搜索，再跑布尔完全背包，因为已经把桶的大小排过序了，那么如果可以拼成体积为q的就直接输出结束程序就可以了。

S2 注意两个小错误。

第一个，在最初的那一遍完全背包中，如果f[j-a[i]]+value等于f[j]，那也要把vis[j]设为1，因为这样会最优——在同样的f[j]下，如果vis[j]=1，那么f[j+a[i]]的值会少加1，从而保证最终的结果最优。

第二个，这个真是无语，小错误害死人啊。在搜索完的那次完全背包中，我的初始化不是g[i]=big，而是g[q]=big……手一滑，三个人检查了一个小时，死活检查不出来，从网上下了数据才出来的……检查的时候一定要一个字一个字仔细看，不要因为语句简单就不看了，简单的语句也可能手滑打错。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define rint register int
#define inv inline void
#define big 1e9
using namespace std;
int p,q,a[101],f[20001],que[101],cnt;
bool use[101],vis[20001],g[20001];
inv dp()
{
    for (rint i=0;i<=q;i++) g[i]=0;g[0]=1;
    for (rint i=1;i<=f[q];i++)
        for (rint j=a[que[i]];j<=q;j++)
            if (g[j-a[que[i]]]) g[j]=1;
    if (g[q])
    {
        printf("%d ",f[q]);
        for (rint i=1;i<=f[q];i++) printf("%d ",a[que[i]]);
        exit(0);
    }
}
inv dfs(int x,int dep)
{
    if (dep==f[q]) 
    {
        dp();
        return;
    }
    if (f[q]-dep>p-x) return;
    for (rint i=x+1;i<=p;i++)
    {
        que[dep+1]=i;
        dfs(i,dep+1);
    }
}
int main()
{
    scanf("%d%d",&q,&p);
    for (rint i=1;i<=p;i++) scanf("%d",&a[i]);
    sort(a+1,a+p+1);
    for (rint i=0;i<=q;i++) f[i]=big;f[0]=0;    
    for (rint i=1;i<=p;i++)
        for (rint j=0;j<=q;j++)
        {
            vis[j]=0;
            if (j>=a[i])
            {
                int value=vis[j-a[i]]^1;
                if (f[j-a[i]]+value<=f[j])
                {
                    f[j]=f[j-a[i]]+value;
                    vis[j]=1;
                }
            }
        }
    dfs(0,0);
}

总结：

  1. 要思考一下第一个搜出来的是不是最优解，是的话可以直接剪掉。

  2. 一定要注意细节，等于号加不加是个问题，仔细思考。出错的时候一句一句认真检查，千万不要嫌麻烦，发愁的时间比检查的时间长多了。