双袋购物

public class Main {
  public static void main(String[] args) {
    java.util.Scanner sc = new java.util.Scanner(System.in);
    int n=sc.nextInt(), A=sc.nextInt(), B=sc.nextInt(), i, j, maxVal=0;
    int bagA[]=new int[A+5], bagB[]=new int[B+5], ansA[]=new int [n+5],
        ansB[]=new int[n+5], volume[]=new int[n+5], value[]=new int[n+5];
    for (i = 1; i <= n; ++i) {
      volume[i] = sc.nextInt();
      value[i] = sc.nextInt();
      for (j = A; j >= volume[i]; --j)//对袋子1进行动态规划
        bagA[j] = Math.max(bagA[j], bagA[j-volume[i]] + value[i]);
      ansA[i] = bagA[A];//ansA[i]:一直使用袋子1到第i个节点时的最大总价值
    }
    for (i = n; i > 0; --i) {//对袋子2进行动态规划，反向进行
      for (j = B; j >= volume[i]; --j)
        bagB[j] = Math.max(bagB[j], bagB[j-volume[i]] + value[i]);
      ansB[i] = bagB[B];//ansB[i]:使用袋子2从第i个节点到最后的最大总价值
    }
    for (i = 0; i <= n; ++i)//求在各个节点换袋子的决策能得到的最大总价值
      maxVal = Math.max(maxVal, ansA[i] + ansB[i+1]);
    System.out.println(maxVal);//时间复杂度:O(n*(A+B))
  }
}