同USACO5.3 Milk Measuring
观察数据范围，我们就想到了dfs，而由于题目要求桶数尽量小，很明显可以用迭代加深限制层数求解。
那么，大致思路就是：枚举桶的方案——判断是否可行——可行退出，输出答案。
枚举部分毫无疑问的dfs。判断部分用完全背包。这样就解决了此题。
C++代码：

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
inline int rd(){
    char c=getchar();
    while(!isdigit(c))c=getchar();
    int x=c-48;
    for(c=getchar();isdigit(c);c=getchar())x=(x<<3)+(x<<1)+c-48;
    return x;
}
short buf[10];
inline void wt(int x){
    int l=-1;
    while(x>9){
        buf[++l]=x%10;
        x/=10;
    }
    putchar(x+48);
    while(l>=0)putchar(buf[l--]+48);
}  //IO优化，卡常数
int a[105],st[105],l=-1,q,n;  //st是栈，l是栈顶指针
bool f[20005];  //dp用
bool dp(){
    int i,j;
    memset(f,0,sizeof(f));
    f[0]=1;
    for(i=0;i<=l;i++){
        for(j=st[i];j<=q;j++)if(f[j-st[i]])f[j]=1;  //完全背包
        if(f[q])return 1;  //小优化：可以让速度加快很多
    }
    return 0;
}
bool dfs(int h,int maxh){
    if(l==maxh-1)return dp();
    if(h==n-1){
        if(dp())return 1;
        st[++l]=a[h];
        if(dp())return 1;
        l--;
        return 0;
    }  //递归边界单独处理
    st[++l]=a[h];
    if(dp()||dfs(h+1,maxh))return 1;
    l--;
    return dfs(h+1,maxh);  //分情况
}
int main(){
    int i;
    q=rd();n=rd();
    for(i=0;i<n;i++)a[i]=rd();
    sort(a,a+n);  //题目没说桶是排好序的，加了保险
    for(i=1;;i++)if(dfs(0,i))break;  //迭代加深
    wt(l+1);
    for(i=0;i<=l;i++){
        putchar(' ');
        wt(st[i]);
    }
    return 0;
}

PS.此题也可以全用dp，记f(i,j)为用前i个桶拼出j的容量的最小桶数，当作完全背包求解。速度比dfs快，但打印方案比较困难。

看这里看这里！非爆搜呦~
先dp一次算最小需要的桶数
然后根据桶数记忆化搜索
93ms

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i <= _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i >= _##i; --i)
#define mem(f,x) memset(f,x,sizeof(f))
//========================================================================
int f[20005];
int c[105];
int v[20005];
int link[20005];
int n, m;
int cmp(int A, int a, int B, int b) {
    if (a == 0 || b == 0) {
        if (v[A] < v[B]) return 1;
        if (v[A] > v[B]) return -1;
        return 0;
    }
    int temp = cmp(a, link[a], b, link[b]);
    if (temp == 0) {
        if (v[A - a] < v[B - b]) return 1;
        if (v[A - a] > v[B - b]) return -1;
        return 0;
    }
    else {
        return temp;
    }
}
void dfs(int x, int y) {
    if (link[x] != -1) return;
    if (y == 1) {
        link[x] = 0;
        return;
    }
    FORD(i, x - 1, 1) {
        if (f[i] == y - 1) {
            if (v[x - i] == -1) continue;
            dfs(i, y - 1);
            if (link[x] == -1) {
                link[x] = i;
            }
            else {
                if (cmp(x, i, x, link[x]) > 0)
                    link[x] = i;
            }
        }
    }
}
int main()
{
    cin >> m >> n;
    FOR(i, 1, n) cin >> c[i];
    FOR(k, 1, n - 1) {
        FOR(j, 1, n - k) {
            if (c[j] > c[j + 1]) {
                int t = c[j];
                c[j] = c[j + 1];
                c[j + 1] = t;
            }
        }
    }
    mem(f, 0x7f);
    f[0] = 0;
    FOR(k, 1, n) {
        int minx;
        int j;
        FOR(i, 0, c[k] - 1) {
            j = i + c[k];
            minx = f[i] + 1;
            while (j <= m) {
                if (f[j] + 1 < minx) {
                    minx = f[j] + 1;
                }
                else {
                    f[j] = min(f[j], minx);
                }
                j += c[k];
            }
        }
    }
    cout << f[m] << " ";
    mem(v, -1);
    FOR(k, 1, n) {
        FOR(i, 1, m) {
            if (v[i] != -1) continue;
            if ((i%c[k]) == 0) v[i] = k;
        }
    }
    mem(link, -1);
    dfs(m, f[m]);
    vector<int> ans = {};
    int tmpm = m;
    while (link[tmpm] != 0) {
        ans.push_back(v[tmpm - link[tmpm]]);
        tmpm = link[tmpm];
    }
    ans.push_back(v[tmpm]);
    FORD(i, (int)ans.size() - 1, 1)
        cout << c[ans[i]] << " ";
    cout << c[ans[0]];
    return 0;
}

/*
USACO的一道题目改了个背景~好题
搜索+背包dp~
我们看到我们根本很难去搜索
如果去枚举选取哪些再判断可行的话
那么我们会有2^100种情况检查
必然是会爆炸的~
这样我们其实可以采用迭代加深搜索的方法
这样完全是可行的
因为这样完全可以减少一些使用了全部水桶的方案
只要找到一个解就退出也是挺快的
即我们从1...n枚举最大深度上线maxd
然后再枚举选取这maxd个元素~这里用dfs来解决
选取好后开始检查这maxd个元素是否可以填满V容量
这像不像是背包?
因为每个水桶可以用无限多次
所以我们可以用完全背包来解决
因为只需要判断是否能装满所以我们用f[]的0或1来表示能否到达
然后完全背包刷一遍即可
这里可以用递推地方法也可以用递归的方法~
窝两个都写了一下
递归会比递推快很多~因为递推要全部刷一遍复杂度是O(nV)的
而递归递归下去找到一个可行解就是连续递归返回
所以效率高了很多(220ms-45ms)
这样就可以解决这道题了~
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=105;
const int MAXV=21000;
int f[MAXV];
int a[MAXN];
int v[MAXN];
int V,n;
int maxd;

void init()
{
    scanf("%d%d",&V,&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&v[i]);
}

void print()
{
    printf("%d ",maxd);
    for(int i=1;i<=maxd;i++)
        printf("%d ",a[i]);
    exit(0);
}

/*bool check(int& V)
{
    memset(f,0,sizeof(f));  f[0]=1;
    for(int i=1;i<=maxd;i++)
        for(int j=0;j<=V;j++)
            if(f[j]&&j+a[i]<=V)
                f[j+a[i]]=1;
    return f[V];
}*/

bool check(int x)
{
    int &s=f[x];
    if(s!=-1)
        return s;
    if(x==0)
        return s=1;
    for(int i=1;i<=maxd;i++)
        if(x>=a[i]&&check(x-a[i]))//第一次进入是从此入口递归下降
            return s=1;
    return s=0;
}

void dfs(int depth,int k)//当前在选第cur个位置,到了第k个水桶
{
    if(depth==maxd+1)
    {
        memset(f,-1,sizeof(f));
        if(check(V))
            print();
        return;
    }
    if(k>n)
        return;
    a[depth]=v[k];
    dfs(depth+1,k+1);//选了了该水桶
    dfs(depth,k+1);//没选该水桶(巧妙利用了覆盖)
}

void id_dfs()
{
    sort(v+1,v+n+1);
    n=unique(v+1,v+n+1)-v-1;//优化程度不大(数据重合少)
    for(maxd=1;maxd<=n;maxd++)
        dfs(1,1);
}

int main()
{
    init();
    id_dfs();
}
     

因为是一道 迭代加深搜索 ，所以没什么可说的。

普及一下： 迭代加深搜索 是\(dfs\)和\(bfs\)的结合体，其搜索方法为：

每次规定一个搜索深度\(d\)，让\(dfs\)在\(d\)层之内搜索。

然后不断增大\(d\)，知道答案不符合为止。

而本题恰好符合两个条件：深度不确定、状态巨大。

所以\(dfs\)和\(bfs\)都无法满足喽！

\(d\)表示用桶的个数。

//迭代加深搜索 
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
    int x=0;while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;}

int n,m,a[110];
int d;
int q[110];
bool f[21000];
inline bool check(){
    for(int i=1;i<=m;i++) f[i]=false;
    f[0]=true;
    for(int i=1;i<=d;i++)
    for(int j=0;j+q[i]<=m;j++) f[j+q[i]]|=f[j];
        //背包写法 O(m)
    return f[m];     
}
inline bool dfs(int x,int y) {
    //从y到n选
    //让桶的大小递增 
    if(x>d) return check(); 
    for(int i=y;i<=n;i++) {
        q[x]=a[i];
        if(dfs(x+1,i+1)) return true;
    } return false;
}

int main(){
    m=read(),n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+1+n);
    for(d=1;;d++)
        if(dfs(1,1)) break;
    printf("%d ",d);
    for(int i=1;i<=d;i++) printf("%d ",q[i]);
    putchar('\n');  
    return 0;
}

//Discribe:
/*
dfs+dp 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>
#include <climits>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
int p,q;
int useNum=0;
int num[105]={0},dp[20005]={0},ans[105]={0};

bool can(int left)//剩余left容量能否倒满 
{
    if (dp[left] != -1)//已经确定 
        return dp[left];
    if (left == 0)//倒满了 
        return dp[left] = 1;
    for (int i = 0; i < useNum; i++)//枚举每一个桶 
        if (left >= ans[i] && can(left - ans[i]))//桶还能倒水，继续 
            return dp[left] = 1;
    return dp[left] = 0;
}

void dfs(int total, int now)//total：现在第几个桶。now：已经放了几个桶 
{
    if (now == useNum)//放完了 
    {
        memset(dp, -1, sizeof dp);//初始化 
        if (can(q))
        {
            printf("%d", useNum);//输出桶数 
            for (int i = 0; i < now; i++)
                printf(" %d", ans[i]);
            puts("");
            exit(0);//退出整个程序 
        }
        return;
    }
    if (total >= p)//边界 
        return;
    ans[now] = num[total];//记录答案 
    dfs(total + 1, now + 1);//买这个桶 
    dfs(total + 1, now);//不买这个桶
    //前面两行顺序不能颠倒！！！ 
}
int main()
{
    //freopen("water.in","r",stdin);
    //freopen("water.out","w",stdout);
    scanf("%d%d",&q,&p);
    for (int i=0;i<p;i++) {
        scanf("%d",&num[i]);
    }
    sort(num,num+p);//排序 
    for (useNum=1;useNum<=p;useNum++) {//枚举使用桶数 
        dfs(0,0);//dfs一发 
    }
    return 0;
}

//不加注释的代码都是耍流氓
#include <iostream>
#include <cctype>
#include <climits>
#include <stack>
#include <algorithm>
#include <cstring>
using namespace std;
#define N 1001
#define M 20001
int a[N]={0},k,q,p,ans[N]={0};
int f[M];
bool can(int n)
{
    int &zz=f[n];
    if(n==0)
        return zz=1;
    if(zz>=0)//记忆化搜索
        return zz;
    for(int i=1;i<=k;i++)
        if(n>=ans[i]&&can(n-ans[i]))
            return zz=1;
    return zz=0;
}
void dfs(int n,int m)//n表示做到多少 m表示第几个桶
{
    if(m==k+1)//全部做完了
    {
        memset(f,-1,sizeof(f));
        if(can(q))//如果容积q可以的话
        {
            cout<<k<<" ";
            for(int i=1;i<m;i++)
                cout<<ans[i]<<" ";
            cout<<endl;
            exit(0);//完全结束
        }
        return ;//这个return很重要
    }
    if(n>p)//递归边界
        return ;
    ans[m]=a[n];
    dfs(n+1,m+1);//选第m个桶
    dfs(n+1,m);//不选第m个桶
}
int main()
{
    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++)//枚举K个桶的情况
        dfs(1,1);
}

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int VMAXN = 2e4 + 10;
const int TMAXN = 100 + 10;
const int INF = 0x3f3f3f3f;
 
int num[TMAXN], dp[VMAXN], k, n, m;
int ans[TMAXN];
 
bool Check(int sum)
{
    int &cur = dp[sum];
    if (cur != -1)
        return cur;
    if (sum == 0)
        return cur = 1;
    for (int i = 0; i < k; i++)
        if (sum >= ans[i] && Check(sum - ans[i]))
            return cur = 1;
    return cur = 0;
}
 
void DFSID(int cur, int dep)
{
    if (dep == k)
    {
        memset(dp, -1, sizeof dp);
        if (Check(n))
        {
            printf("%d", k);
            for (int i = 0; i < dep; i++)
                printf(" %d", ans[i]);
            puts("");
            exit(0);
        }
        return;
    }
    if (cur >= m)
        return;
    ans[dep] = num[cur];
    DFSID(cur + 1, dep + 1);
    DFSID(cur + 1, dep);
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int i, j;
    scanf("%d%d", &n, &m);
    for (i = 0; i < m; i++)
        scanf("%d", &num[i]);
    sort(num, num + m);
    for (k = 1; k <= m; k++)
        DFSID(0, 0);
    return 0;
}

这题太·········

刚开始是在想不通为什么一个很烂的dfs+dp会秒杀。。
后来才知道，输入的数据是不水的，但是输出的答案是很水的
导致你在搜索长度为3的序列时就会得到答案。
首先按照长度，搜索出所有满足的序列，然后把这个序列扔到dp里，有答案就直接halt。
思路还是比较的清晰，但我想不是正解，因为如果不是因为数据水，肯定不会秒杀
如果哪位大牛，有详细思路，或者有一些其他看法欢迎+我QQ841249284
大家一起搞竞赛!
DXE-SYF

额，DFSID+DP竟然0ms，不过这个应该很好卡吧！随便设计个数据就会卡

靠，题目都看不懂，什么意思啊

DFSID

题解：http://254117343.blog.163.com/

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

昔日多少次的提交，才换来如今的AC！

这个我没有搜索，而是分两步做的。第一步显然背包就行了。这里我们求出了每个点的最少需要的桶的种类数。然后我们进行枚举。

预处理can[i]表示能用一个桶装满容量为i的容器的最小桶编号。比如有桶容量分别是2,3,那么装满容量为6的容器的最小桶编号为1，所以can[6]=1

假如我们第一步背包的结果保存在数组DP中，dp[i]表示i容量的缸所需最少桶数。

接下来开两个数组记录符合条件的转移值。一开始数组1中只有一个元素m，然后枚举所有dp值为dp[m]-1的元素，不妨设为a1..ak，那么我们取t=min{can[m-ai],1

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 275ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 134ms

├ 测试数据 09：答案正确... 56ms

├ 测试数据 10：答案正确... 134ms

恩，我感到十分自豪。

大家都用搜索。我用Dp哈。

时间复杂度为p*q*p*q/p;

理论上讲是20000*20000*100；

but它过了。

只能说数据太弱了。

完全背包不能用n*c的要用n*c*c/n的否则会破坏字典序。

代码如下：

type node=set of 1..100;

var f:array[0..20000]of longint;

num:array[0..20000]of node;

a:array[1..100]of longint;

p,q,i,j,t,k:longint;

function pd(a,b:node):boolean;

var i:longint;

begin

for i:=1 to 100 do

begin

if (i in a) and not (i in b) then exit(true);

if not (i in a)and (i in b) then exit(false);

end;

end;

begin

assign(input,'vj1159.in');reset(input);

assign(output,'vj1159.out');rewrite(output);

readln(q);

for i:=1 to q do f[i]:=maxlongint div 2;

readln(p);

for i:=1 to p do

read(a[i]);

for i:=1 to p do

for j:=i+1 to p do

if a[i]>a[j] then

begin

t:=a[i];a[i]:=a[j];a[j]:=t;

end;

for i:=1 to p do

for j:=1 to q do

for k:=1 to j div a[i] do

if j-a[i]*k>=0 then

if i in num[j-a[i]*k] then

begin

if f[j-a[i]*k]=f[j] then

begin

if pd(num[j-a[i]*k],num[j]) then

begin

num[j]:=num[j-a[i]*k];

end;

end

else

if f[j-a[i]*k]

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 56ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 291ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：347ms

N次AC 我低级了。

两次AC。。。。。

DFSID真是快啊

注意：没加DP呵。。。。。

可惜第一次交忘了加快排了，竟然90分

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 150ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：150ms

加了之后：

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 72ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：72ms

方法不讲了，详见程序：

program vijos_1159;

const

maxN=100;

maxM=20000;

type

TAns=array[1..maxM] of longint;

var

m,n:longint;

a:array[1..maxN] of longint;

ansDeep:longint;

getAns:boolean;

ans,tmp:TAns;

temp:longint;

procedure qSort(l,r:longint);

var

i,j,x:longint;

begin

i:=l;

j:=r;

x:=a[(i+j)>>1];

repeat

while a[i]x do dec(j);

if ij;

if il then qSort(l,j);

end;

procedure init;

var

i:longint;

begin

readln(m);

readln(n);

for i:=1 to n do

readln(a[i]);

qSort(1,n);

end;

function better(t:TAns):boolean;

var

i:longint;

begin

for i:=1 to ansDeep do begin

if ans[i]t[i] then exit(true);

end;

exit(false);

end;

procedure ID(deep,weight,i:longint);

var

w:longint;

begin

if deep=ansDeep then begin

if weight=m then begin

if not getAns then ans:=tmp

else if better(tmp) then ans:=tmp;

getAns:=true;

end;

exit;

end;

if i=n+1 then exit;

ID(deep,weight,i+1);

w:=weight+a[i];

if w>m then exit;

tmp[deep+1]:=a[i];

while w

想不通列，，，，为什么纯dp不行啊。。。。哪里有后向性、？哪位大牛能给沙茶我解释下么。。。？

同一个程序，一个90，一个AC，BS评测机。

第一问DP不用说，第二问考虑使用ID-DFS（用DP比较麻烦，比较决策需要比较序列的字典序），也就是设置一个上限max,不断放大max，然后DFS找出可行的最优方案中，前max个桶中字典序最小的桶。这样搜的好处是放大的时候利于剪枝。

搜索+DP~~

不过想像各位大牛一样秒杀应该怎么做呢？