思路:
)一眼看过去就可以知道是典型的二维背包,但是卡在了背包容量的变化,仔细想一下就会发现,每加上一个小于k容量的物品,就相当于容量增加了,这个至关重要,可以让我们进行后续背包容量的预处理,详情看代码块注释**
public class Main{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
List<Integer> a=new ArrayList<>();
List <Integer> b=new ArrayList<>();
int sum=0;
int ans=0;
int cnt=0;
for (int i = 1; i <= n; i++) {
int aa=sc.nextInt();
int bb=sc.nextInt();
if(bb<=k){
sum+=bb;//这里记录已经用的总容量
ans+=aa;//提前记录必选的物品的价值
cnt++;//记录此时一共收纳多少个物品
}else {
a.add(aa);
b.add(bb-k);//这里减一下就是为了处理背包容量,使动态背包转化为静态背包
}
}
int tatol=cnt*k-sum;//计算静态背包总容量
int dp[]=new int[tatol+1];//定义dp数组
//经典代码不多做解释,自己理解
for (int i = 0; i < a.size(); i++) {
for (int j = tatol; j >=b.get(i) ; j--) {
dp[j]=Math.max(dp[j],dp[j-b.get(i)]+a.get(i));
}
}
System.out.println(ans+dp[tatol]);//这里打印的时候,一定别忘了加上先前的ans
}
}