AcWing 7. 混合背包问题 Java版题解
原题链接
中等
作者:
小赵想滑板
,
2024-01-23 15:59:36
,
所有人可见
,
阅读 38
Java 代码
import java.util.*;
public class Main{
public static void main(String[]args){
Scanner sc=new Scanner(System.in);
int N=1010;
int n,m;
int f[]=new int[N];
n=sc.nextInt();
m=sc.nextInt();
for(int i=0;i<n;i++){
int v,w,s;
v=sc.nextInt();
w=sc.nextInt();
s=sc.nextInt();
if(s==0){//完全背包类型
for (int j=v;j<=m;j++) f[j]=Math.max(f[j],f[j-v]+w);
}else{
if(s==-1) s=1;
for(int k=1;k<=s;k*=2){
for(int j=m;j>=k*v;j--) f[j]=Math.max(f[j],f[j-k*v]+k*w);
s-=k;
}
if(s>0){
for(int j=m;j>=s*v;j--) f[j]=Math.max(f[j],f[j-s*v]+s*w);
}
}
}
System.out.println(f[m]);
}}