算法提高课汇总

算法思路

多重背包问题:

1. 限制
   • 价格<-->体积
   • 物品数量限制$s_i$
2. 目标
   • 价值Max

详细思路可以参考背包问题.

代码实现

朴素版本 $O(N\times V\times S) = 500\times 6000\times 10 = 3\times 10^7$

#include <iostream>
#include <algorithm>

using namespace std;

const int M = 6010;

int n, m;
int dp[M];

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

    return 0;
}

这里在简单复习以下单调队列优化版本的实现吧.

单调队列 $O(N\times V)$

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, M = 6010;

int n, m;
int dp[N][M];
int q[M];

int main()
{
    cin >> n >> m;
    for( int i = 1; i <= n; i ++ )
    {
        int v, w, s;
        cin >> v >> w >> s;
        for( int r = 0; r < v; r ++ )
        {//余数构成v类
            int tt = -1, hh = 0; //每一类用单调队列求解
            for( int j = r; j <= m; j += v )
            {
                while( hh <= tt && (j - q[hh]) / v > s )    hh ++; //窗口向右滑动一格
                while( hh <= tt && dp[i - 1][j] >= dp[i - 1][q[tt]] + (j - q[tt]) / v * w ) tt --;
                q[ ++ tt ]  = j;
                dp[i][j] = dp[i - 1][ q[hh] ] + ( j - q[hh] ) / v * w; 
             }
        }
    }
    cout << dp[n][m] << endl;

    return 0;
}