算法提高课汇总

算法思路

草药🌿的选择不需考虑不同草药间的关系, 只需考虑选择草药的集合—组合问题; 每个草药可选数目为$[0,1]$.
所以问题可以抽象为01背包问题, 其中

• 限制条件: 采草药🌿的时间, 对应01背包中的体积

• 目标: 价值Max

代码实现

直接应用01背包代码 :

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, M = 1010;

int n, m;
int v[N], w[N];
int dp[M];

int main()
{
    cin >> m >> n;
    for( int i = 1; i <= n; i ++ )  cin >> v[i] >> w[i];

    for( int i = 1; i <= n; i ++ )
    {
        for( int j = m; j >= v[i]; j -- )   dp[j] = max( dp[j], dp[j - v[i]] + w[i] );
    }
    cout << dp[m] << endl;

    return 0;
}