\(USACO\) \(2012\) \(Mar\) \(Gold\) \(T3\) ， \(Luogu\) \(P3052/BZOJ2621\)
给定 \(n\) 个物品各自的权值 \(a_i\) ，求一种组数最少的分组方案使得每组的权值和不超过 \(w\) 。输出这个最小的组数。
从朴素解法开始：由于 \(n \leqslant 18\) ，故不难想到将所有物品从左往右排成一列，压成一个二进制数。其中第 \(i\) 位为 \(1\) 就表示序列第 \(i+1\) 个元素已经被选在该状态里了。同时记录当前状态的权值和，若比 \(w\) 大则要打不合法标记。
然后就是从 \(0\) 状态开始搜索，搜到 \(2^n-1\) 状态即可。对于每一个当前状态 \(x\) ，都枚举所有的合法状态 \(y\) ，能转移的条件是 \(x \wedge^{[1]} y=0\) ，转移到的状态是\(x \vee^{[2]} y\) 。
这样就可以获得 \(10pts\) 的好成绩。因为状态实在是太多辣 \(QWQ\)
考虑优化这个过程：显然，最终答案不会超过 \(n\) 。而且你可以大力猜测答案一定在搜索树不太深的位置。不妨改用迭代加深，逐渐变大组数限制再搜索，减少无用分枝的搜索次数。虽然在浅层多搜索了几次，但耗费的这些时间与我们节省下来的时间相比是微不足道的。
具体的搜索方法是，从小往大限制最多允许分成多少组。每次在序列里从左往右搜索，将当前数确定在某个组里（若权值和不超过 \(w\) ）或者新开一个组，并更新被分到的组的权值和，继续搜索。最后回溯即可。可行性剪枝是当前分出的组数超过限制组数就停止；最优性剪枝是已经搜出了一种合法方案就停止。只要没有被减去且搜完了所有数就是一种合法方案，打好标记直接输出即可。
从运行结果来看，答案确实在搜索树不太深的位置，且剪枝非常有效。
开始搜索之前，不妨考虑一下还有什么办法可以优化搜索的顺序。显然，把大的权值放在前面更加有利于搜索过程中快速剪去答案限制小的部分，更容易快速逼近答案。于是对权值从大到小排个序再开始搜索即可。可以节省 \(\frac{2}{3}\) 的时间。
考虑换一种思路优化朴素解法：由于物品状态不超过 \(2^n\) ，不妨使用状态压缩 \(DP\) 。自然地，设 \(f_x\) 表示到达状态 \(x\) 所需要的最小步数。则转移显然有 \(f_x=\min_\limits{y \subseteq x} \{ f_{x-y}+1 \}\) ，初始值为 \(f_0=0\) ，答案就是 \(f_{2^n-1}\) 。
\(O(3^n)\) 枚举子集的方法：设当前集合为 \(x\) ，转移变量为 \(y\) 。则只要 \(y>0\) ，就不断地把 \((y-1) \wedge i\) 即可。
当然，也可以考虑一下还有什么办法可以优化 \(DP\) 的顺序。显然，把小的权值放在前面更加有利于将不合法的部分集中，有利于 \(DP\) 过程。于是对权值从小到大排个序再开始 \(DP\) 即可。可以节省 \(\frac{4}{9}\) 的时间。
\(View\) \(Code\)
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int ret=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
ret=(ret<<1)+(ret<<3)+ch-'0';
ch=getchar();
}
return ret*f;
}
int n,w,a[19];
long long s[19];
bool flag;
inline bool cmp(int x,int y)
{
return y<x;
}
void dfs(int pos,int groupnum,int grouplimit)
{
if(grouplimit<groupnum||flag)
return;
if(pos==n+1)
{
flag=1;
return;
}
for(register int i=1;i<=groupnum;i++)
{
if(s[i]+a[pos]<=w)
{
s[i]+=a[pos];
dfs(pos+1,groupnum,grouplimit);
s[i]-=a[pos];
}
}
s[groupnum+1]+=a[pos];
dfs(pos+1,groupnum+1,grouplimit);
s[groupnum+1]-=a[pos];
}
int main()
{
n=read();
w=read();
for(register int i=1;i<=n;i++)
a[i]=read();
sort(a+1,a+n+1,cmp);
for(register int i=1;i<=n;i++)
{
flag=0;
dfs(1,0,i);
if(flag)
{
printf("%d\n",i);
return 0;
}
}
return 0;
} \(View\) \(Code\)
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int ret=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
ret=(ret<<1)+(ret<<3)+ch-'0';
ch=getchar();
}
return ret*f;
}
int n,w,a[19],f[262145];
long long sum[262145];
bool illegal[262145],vis[262145];
int main()
{
n=read();
w=read();
for(register int i=1;i<=n;i++)
a[i]=read();
sort(a+1,a+n+1);
for(register int i=1;i<(1<<n);i++)
{
for(register int j=0;j<n;j++)
{
if(i&(1<<j))
sum[i]+=a[j+1];
if(w<sum[i])
{
illegal[i]=1;
break;
}
}
}
memset(f,0x3f,sizeof(f));
f[0]=0;
for(register int i=1;i<(1<<n);i++)
{
for(register int j=i;j;j=i&(j-1))
{
if(illegal[j])
continue;
if(f[i-j]+1<f[i])
f[i]=f[i-j]+1;
}
}
printf("%d\n",f[(1<<n)-1]);
return 0;
}\([1]\) ： \(\wedge\) 表示逻辑与运算。
\([2]\) ： \(\vee\) 表示逻辑或运算。
$Luogu$ $P3052$ $[USACO12MAR]$ 摩天大楼里的奶牛 $Cows$ $in$ $a$ $Skyscraper$
原文：https://www.cnblogs.com/Peter0701/p/11726290.html