AcWing 6. 多重背包问题 III(Java代码>Deque)
原题链接
困难
作者:
Demo_5
,
2023-11-16 20:21:22
,
所有人可见
,
阅读 54
代码
import java.util.*;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N+1];
int[] w = new int[N+1];
int[] s = new int[N+1];
int[][] f = new int[N+1][V+1];
for(int i = 1;i <= N;i++){
v[i] = sc.nextInt();
w[i] = sc.nextInt();
s[i] = sc.nextInt();
}
//队列表示范围内的能取到的最大价值的体积
Deque<Integer> deq;
for(int i = 1;i <= N;i++){
//核心,按照余数不同进行分类
for(int r = 0;r < v[i];r++){
deq = new LinkedList<>();
for(int j = r;j <= V;j+=v[i]){
f[i][j] = f[i-1][j];
//控制滑动窗口大小
while(!deq.isEmpty() && j - deq.peekFirst() > s[i]*v[i])deq.pollFirst();
//滑动窗口最大值保存在队列头
while(!deq.isEmpty() && f[i-1][deq.peekLast()]+(j-deq.peekLast())/v[i]*w[i] <= f[i-1][j])deq.pollLast();
//加入新元素
deq.offerLast(j);
//更新
f[i][j] = f[i-1][deq.peekFirst()]+(j-deq.peekFirst())/v[i]*w[i];
}
}
}
System.out.println(f[N][V]);
}
}