思路:

)一眼看过去就可以知道是典型的二维背包,但是卡在了背包容量的变化,仔细想一下就会发现,每加上一个小于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
    }
}