题解 P1060 【开心的金明】
phigy
·
·
题解
~~**看起来似乎没有dfs 。**~~
------------
这题原本是一道基本的 01 背包 ， 动态规划 。
只需将价格与重要度提前算好 ， 再套模板即可 。
代码如下 ：
```cpp
#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\times10^7$ 。
也就是说可以 dfs !
code :
```cpp
#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+1,s); ///不选
a[i]=1;
dfs(i+1,s+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 ^.^;
}
```
第九个点跑得最慢达到 $908ms$ ， 开氧气可达到 $240ms$ 。
------------
写题解不容易大佬勿喷 ……