C++代码，01背包做法

解题思路:

注意事项:

参考代码:

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

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

代码如下 ：

#include<bits/stdc++.h>//万能头文件

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<30000N<30000 表示总钱，m<25m<25 为希望购买物品的个数 。`

注意：m<25m<25 。

2^{25}<3.5\times10^72 

25

 <3.5×10 

7

  。

也就是说可以 dfs !

code :

#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 ^.^;

}

第九个点跑得最慢达到 908ms908ms ， 开优化可达到 240ms240ms 。