AcWing 5. 多重背包问题 II (Java代码)
原题链接
中等
作者:
Demo_5
,
2023-11-13 15:29:40
,
所有人可见
,
阅读 43
Java代码
import java.io.*;
import java.util.*;
class Main{
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] r = br.readLine().split(" ");
List<T> list = new ArrayList<>();
int N = Integer.parseInt(r[0]);
int V = Integer.parseInt(r[1]);
T t;
int s,v,w;
for(int i = 0;i < N;i++){
r = br.readLine().split(" ");
v = Integer.parseInt(r[0]);
w = Integer.parseInt(r[1]);
s = Integer.parseInt(r[2]);
for(int k = 1;k < s;k *= 2){
t = new T();
t.v = k * v;
t.w = k * w;
list.add(t);
s -= k;
}
if(s > 0){
t = new T();
t.v = v*s;
t.w = w*s;
list.add(t);
}
}
int[] f = new int[V+1];
for(int i = 0;i < list.size();i++){
for(int j = V;j >= list.get(i).v;j--){
f[j] = Math.max(f[j],f[j-list.get(i).v] + list.get(i).w);
}
}
System.out.println(f[V]);
}
}
class T{
int v;
int w;
}