HDOJ2111 Saving HDU（背包问题）

题目链接：​​Saving HDU​​

这题是个背包问题，首先按照单价排序，然后，装的下就装，装不下就分割。

import java.util.Scanner;

//背包问题
public class Main{
  private static Scanner scanner;
  private static int pi[];
  private static int mi[];

  public static void main(String[] args) {
    scanner = new Scanner(System.in);
    while (scanner.hasNext()) {
      int v = scanner.nextInt();// 容量
      if (v == 0) {
        break;
      }
      int n = scanner.nextInt();// 宝贝种类
      pi = new int[n];// 单价
      mi = new int[n];// 体积
      for (int i = 0; i < n; i++) {
        pi[i] = scanner.nextInt();
        mi[i] = scanner.nextInt();
      }
      // 按照单价排序
      sort();
      // for (int i = 0; i < n; i++) {
      // System.out.println(pi[i]+","+mi[i]);
      // }
      int sum = 0;// 总价值
      for (int i = 0; i < n; i++) {
        if (mi[i] >= v) {// 来到这里就一定可以装满
          sum += v * pi[i];
          break;
        } else {
          sum += pi[i] * mi[i];
          v -= mi[i];
          // v重新表示为：背包剩余容量
        }
      }
      System.out.println(sum);
    }
  }

  private static void sort() {
    for (int i = 0; i < pi.length - 1; i++) {
      for (int j = i + 1; j < pi.length; j++) {
        if (pi[i] < pi[j]) {
          int temp = pi[i];
          pi[i] = pi[j];
          pi[j] = temp;

          temp = mi[i];
          mi[i] = mi[j];
          mi[j] = temp;
        }
      }
    }
  }
}