B1068 Find More Coins (01背包,dfs+

B1068 Find More Coins (30分)

一串数字里求满足相加等于m的最小序列。
//两种做法，01背包来说是题模板题了，但好像已经属于顶级考纲了，先考虑dfs，dfs最后一个测试点会卡你一处。

• dfs+减枝

注意：对于每种硬币有取和不取，n个硬币（不是n种），所有不能以book[i]==1来回溯，改成book[i]++.

• 原思路：
  把n个数字存进数组a，dfs时从[1,n]遍历数组a，因为有可能数组是1，1，1，2，3，4，数组下标不同但重复遍历了许多次1
• 改进思路：
  所有的数只记录一遍进数组a[]。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#define lowbit(i)((i)&(-i))
using namespace std;
typedef long long ll;
const int MAX=1e5+10;
const int INF=0x3f3f3f3f;
const int MOD=1000000007;
const int SQR=632;//633块，632个
int n,m,t=1;
int a[MAX],pre[MAX],book[MAX];
int flag=0;
void dfs(int index,int sum)
{
    if(sum>m||flag)
        return ;
    else if(sum==m&&flag==0)
    {
        for(int i=1;i<index;i++)
        {
            if(i==1)
                cout<<pre[i];
            else
                cout<<" "<<pre[i];
        }
        flag=1;
        return ;
    }
    for(int i=1;i<=t;i++)
    {
        if(book[a[i]]>0)
        {
            pre[index]=a[i];
            book[a[i]]--;
            dfs(index+1,sum+a[i]);
            book[a[i]]++;
        }
    }

}
int main()
{
    memset(book,0,sizeof(book));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        if(x<=m)
        {
            if(book[x]==0)
                a[t++]=x;
            book[x]++;
        }
    }
    sort(a+1,a+t);
    dfs(1,0);
    if(flag==0)
        cout<<"No Solution"<<endl;
    return 0;
}
-------
- ### 01背包
放着