AcWing 1019. 庆功会

题目传送门

一、题目解析

这还解析个啥，傻子都知道这是一道多重背包的裸题，而且看了一下数据范围，\(500*6000*10\)=\(3e7\),\(C++\)一秒可过，这是在玩啥啊！

二、朴素版本解法

#include 

using namespace std;

//多重背包问题，每件物品的数量是有限制的，不是无穷，也不是只有1个。
// 状态表示  集合，属性
// 状态计算

const int N = 110;

int n, m;
int v[N], w[N], s[N];
int f[N];

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];

    for (int i = 1; i <= n; i++)
        for (int j = m; j >= v[i]; j--)
            for (int k = 0; k <= s[i] && k * v[i] <= j; k++) //穷举所有可能性，尝试拿到最大的合理值
                f[j] = max(f[j], f[j - v[i] * k] + w[i] * k);

    cout << f[m] << endl;
    return 0;
}

三、二进制优化版本解法

#include 

using namespace std;
const int N = 12010;
int n, m;
int v[N], w[N];
int f[N];
int idx;
//多重背包的二进制优化
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int vi, wi, si;
        cin >> vi >> wi >> si;//二进制优化,能打包则打包之，1,2,4,8,16,...
        int b = 1;
        while (b <= si) {
            v[++idx] = vi * b;
            w[idx] = wi * b;
            si -= b;
            b *= 2;
        }
        //剩下的
        if (si > 0) {
            v[++idx] = vi * si;
            w[idx] = wi * si;
        }
    }
    for (int i = 1; i <= idx; i++)
        for (int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    printf("%d", f[m]);
    return 0;
}

四、单调队列优化版本

#include 

using namespace std;
const int N = 20010;
typedef pair PII;
PII q[N]; //单调队列数组
// 第一维：背包能装下多少个i物品 k=[0~m/v],用来控制滑动窗口的长度
// 第二维：真正滑动窗口中数据的值(单调队列)
int f[N]; //dp数组

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    //n类物品逐个加入讨论
    for (int i = 1; i <= n; i++) {
        int v, w, s;//体积，价值，个数
        cin >> v >> w >> s;
        //按余数j进行分类讨论
        for (int j = 0; j < v; j++) {
            int hh = 0, tt = -1;   //初始化单调队列
            for (int k = 0; k <= m / v; k++) {    //枚举每个可能数量的物品i
                //这个x是准备入队列的数据,通过公式变形得到此形态
                int x = f[k * v + j] - k * w;     //在放入k个物品i的情况下，可以获取到的最优解
                //单调队列中比x小的出队
                while (hh <= tt && x >= q[tt].second) tt--;
                //x存储到单调队列中
                q[++tt].first = k, q[tt].second = x;
                //维护队列头,k-s表示滑动窗口的长度
                if (q[hh].first < k - s) hh++;
                //f[i-1]--->f[i]
                f[k * v + j] = q[hh].second + k * w;
            }
        }
    }
    //输出
    printf("%d\n", f[m]);
}