AcWing 5. java详解
原题链接
中等
作者:
季之秋
,
2021-02-09 14:03:57
,
所有人可见
,
阅读 459
/*
核心:每i个数可以选s[i]次,将s[i]打包成二进制选法,每一位只能选一个或不选,
因为最大值是唯一确定的,可能第i个物品选k次,我们把s[i]打包成二进制,无论k是多少我们都可以
用二进制里面表示,所以转换成二进制问题,第i个物品的哪些位选或不选,
选出来的位加起来凑成了max里i的次数,
状态计算方程(状态转移):将有限次选法拆分打包成二进制选法,每个二进制位选或不选,
这样的话我们就可以用二进制凑出每一种i的选法k,
*/
import java.util.*;
public class Main{
static int N=25000,cnt;
static int[] f=new int[N];
static int[] v=new int[N],w=new int[N];
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
for(int i=1;i<=n;i++){
int a=sc.nextInt();
int b=sc.nextInt();
int s=sc.nextInt();
int k=1;
while(s-k>=0){//二进制打包转化——>01背包问题
cnt++;
v[cnt]=a*k;// 第i个数选1次 、2次 、4次、8次、、
w[cnt]=b*k;
s-=k;
k*=2;
}
if(s>0){//最后可能剩一个不是二进制位的数,所以单独打包
cnt++;
v[cnt]=a*s;
w[cnt]=b*s;
}
//这样一个k次的物品变成了log k次物品,因为log k个数里可以凑出0到k
}
n=cnt;//n个物品变成cnt个物品
for(int i=1;i<=n;i++){
for(int j=m;j>=v[i];j--){
f[j]=Math.max(f[j],f[j-v[i]]+w[i]);
}
}
System.out.println(f[m]);
}
}