开心的金明(附DFS)

看起来似乎没有DFS

---

这题原本是一道基本的 01 背包 ， 动态规划 。

只需将价格与重要度提前算好 ， 再套模板即可 。

代码如下 ：

#include <iostream>

using namespace std;

int f[30][100000];
int w[10000];
int v[10000];

int main()
{
    int n,m;
    int i,j,k;
    cin>>m>>n;
    //提前相乘
    for(i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];
        v[i]*=w[i];
    }
    for(int i=1;i<=n;i++)
    {
        //01背包最关键的位置,为防止反复加同一物品，需要倒着搜，这也是01背包与完全背包的不同之处
        for(int c=0;c<=m;c++)
        {
            f[i][c]=f[i-1][c];
            if(c>=w[i])
            f[i][c]=max(f[i][c],f[i-1][c-w[i]]+v[i]);
        }
    }
    cout<<f[n][m];
    return 0;
}

但不会dp的怎么做呢？
一看数据范围：
其中$N<30000$表示总钱,$m<25$表示希望购买物品的数量
注意$m<25$。
$2^{25}<3.5$ x $10^7$
也就是说可以dfs！

AC代码

#include <iostream>

using namespace std;

int a[30],w[30],v[30],ans,s,N,m;

void dfs(int i,int s)
{
    if (i>=m+1)///选择数量到达
    {
        int t=0;
	    for (int i=1;i<=m;i++)///计算体积和 
        {
            t=t+v[i]*a[i];
	    }
        if (t<=N) ///体积是否小于背包体积
        {   
            if (s>=ans) ///价值和是否大于当前最大价值和
            {
                ans=s;///答案更新 
            }
        }
    }
    else
    {
	    a[i]=0;
       	dfs(i****); ///不选
	    a[i]=1;
	    dfs(i****+v[i]*w[i]);///选
    }
}
int main()
{
   cin>>N>>m;
   for (int i=1; i<=m; i++)
   {
	   cin>>v[i]>>w[i];
   }
   dfs(1,0);
   cout<<ans;
   return 0;
}