13024: 【原3024】有限背包

题目

题目描述

author: snow_sword 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/3024

Description

大家都已经学过了01背包问题，现在这个问题稍微有一些变化：第i种物品可能有pi个，你可以选取任意个（小于pi)。给定背包容量m，求背包能达到的最大价值。

Input Format

第1行有2个整数n, m，表示要有n种物品，背包容量为m 第2到n+1行，每行三个整数pi, wi, vi，分别表示该种物品有pi个，每个物品重wi，价值为vi

Output Format

输出一个数字，表示背包能达到的最大价值。

Sample Input 1

Sample Output1

数据范围

对于80%的数据，1<=n<=1000，1<=m<=1000, 1<=sumP=p1+p2+...+pn<=2000 对于100%的数据，1<=N<=1000, 1<=m<=1000, 1<=pi<=1000

yyong119's solution

#include<cstdio>
#include<cstring>
#include<algorithm>
#include <deque>
#define MAX_N 1010
using namespace std;
int n, m;
int f[MAX_N];
int p[MAX_N], w[MAX_N], v[MAX_N];
deque<int> x, y;

void solve() {

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < w[i]; ++j){
            x.clear(); y.clear();
            for (int k = 0; j + w[i] * k <= m; ++k) {
                int we = j + w[i] * k, va = v[i] * k;
                if (x.size() == p[i] + 1) {
                    if (y.front() == x.front())
                        y.pop_front();
                    x.pop_front();
                }
                int t = f[we] - va;
                x.push_back(t);
                while (!y.empty() && t >= y.back())
                    y.pop_back();
                y.push_back(t);
                f[we] = y.front() + va;
            }
        }
    }
}

int main() {

    scanf("%d%d", &n, &m);
    memset(f, 0, sizeof(f));
    for (int i = 0; i < n; ++i)
        scanf("%d%d%d", &p[i], &w[i], &v[i]);
    solve();
    printf("%d\n", f[m]);
    return 0;
}