6.1 题目描述

小美近来疯狂购物，信用卡上获得积分100000。在积分商城中有许多物品可以选兑。例如食用油，大米，钢笔，电烤炉，研磨机，热水壶等等。信用卡积分就快过期了，小美想将这一万积分尽量用光，请问小美应该怎么办?
小美在挑选物品的过程中，发现有些积分和实际价格的比例大概是100:1，继而发现有些商品在积分商城里购买并不划算，不如去京东购买。小美为了这100000积分也是拼了，将所有商品在京东的价格罗列了出来，同时罗列了所有商品的积分。此时小美又应该怎么挑选，使得获得的价值最大?(或许你应该想想价值是什么?)
不少人问，物品是否可以重复挑选，整数背包问题有两种，bounded knapsack (物品有限)and unbounded knapsack (物品无限)，如果前者将每件相同的物品都视作不同的物品，其实又变成了0-1背包问题，这个我们学过。两种情形，虽然算法书写不同，但本质上没有什么太大区别。
作为练习，这里要求物品有库存量限制。

6.2 程序使用说明

  1. 输入总积分totalScore；
    2. 输入物品种数n；
    3. 依次输入各物品信息goods，即购买积分、京东价格、库存量。

    6.3 分析和设计

  2. 思路
    这个问题与物品有限的背包问题类似，在0-1背包问题中只需要决定某个物品是否选择，也可看做是选0个或者1个，而对于物品有限的背包问题需要决定某个物品选取的个数，可以看做选0个、1个、…、k个。与背包问题比较，这个问题的总积分可以看做背包容量，物品购买积分可看做物品重量，而京东的价格就可以看作物品的价值。所以此问题的递推公式可为：F[i,v] = max{F[i-1,v-kCi] + kWi | 0 <= k <= Mi} Ci代表购买积分、Wi代表京东价格、Mi代表库存。运用动态规划填满物品个数乘以总积分的矩阵就可解决这个问题。
    2. 伪代码
    1. ChooseGoods(goods[1...n, 0...2], totalScore)
    2. // 输入：商品信息goods，goods[i][0]、goods[i][1]、goods[i][2]分别表示//          商品的购买积分、京东价格、库存量， 总积分totalScore
    3. // 输出：每种物品的选择个数
    4. // maxValue记录前i种物品在积分为j时可得到的最大价值与物品i购买个数
    5. maxValue[1...n, 1...totalScore, 0...1] <- 0
    6. for i <- 1 to n do
    7.  for j <- 1 to totalScore do
    8.      // 遍历物品i在积分j的情况下的所有选取可能
    9.      for k <- 0 to goods[i, 2] do
    10.          if goods[i, 0]*k > j
    11.              break
    12.          else 
    13.              value <- goods[i, 1]*k+maxValue[i-1, j-goods[i, 0]*k, 0]
    14.              if value > result[i, j, 0]
    15.                  maxValue[i, j, 0] <- value
    16.                  maxValue[i, j, 1] <- k
    17. choose[1...n] <- 0
    18. nowScore <- totalScore
    19. for i <- n to 1 do
    20.  choose[i] = maxValue[i, nowScore, 1]
    21.  nowScore = nowScore - goods[i, 0] * choose[i]
    22. return choose
  3. 时间复杂度
    在动态规划中，时间复杂度总是填充动态规划表格的时间，在本题中，填一个单元格需要进行商品的库存量次循环，所以此题的时间复杂度为O(ntotalScoremax(库存量))。

    6.4 测试用例

    | | | | | | | —- | —- | —- | —- | —- | | 1 | totalScore = 100000
    n = 2
    Goods = [[50000, 500, 2],
    [50000, 100, 2]] | 2 0 | 2 0 | 通过 | | 2 | totalScore = 100000
    n = 3
    Goods = [[50000, 500, 2],
    [50000, 600, 1],
    [50000, 100, 2]] | 1 1 0 | 1 1 0 | 通过 | | 3 | totalScore = 100000
    n = 3
    Goods = [[50000, 500, 2],
    [50000, 600, 1],
    [5000, 100, 10]] | 0 1 10 | 0 1 10 | 通过 |

6.5 源代码（含注释）

  1. import java.util.Scanner;
  2. public class Knapsack {
  3.     public static void main(String[] args) {
  4.         int[][] goods = new int[][]{{0,0,0},{50000, 500, 2},{50000, 100, 2}};
  5.         int totalScore = 100000;
  6.         int[] choose = chooseGoods(goods, totalScore);
  7.         System.out.println("案例物品状态：\n50000 500 2\n50000 100 2");
  8.         System.out.print("案例购买方式：");
  9.         display(choose);
  10.         Scanner scanner = new Scanner(System.in);
  11.         System.out.print("请输入总积分：");
  12.         totalScore = scanner.nextInt();
  13.         System.out.print("请输入物品种数：");
  14.         int n = scanner.nextInt();
  15.         goods = new int[n+1][3];
  16.         goods[0] = new int[]{0, 0, 0};
  17.         for (int i = 1; i <= n; i++){
  18.             System.out.print("请输入第"+i+"种物品的购买积分、京东价格、库存量：");
  19.             goods[i] = new int[]{scanner.nextInt(), scanner.nextInt(), scanner.nextInt()};
  20.         }
  21.         System.out.print("购买方式：");
  22.         display(chooseGoods(goods, totalScore));
  23.     }
  24.     /**
  25.      * 给出商品的积分、京东价格、库存量，京东价格即为价值，在总价值一定的情况下找出最优的购买方式
  26.      * 递推公式：F[i,v] = max{F[i-1,v-kCi] + kWi | 0 <= k <= Mi} Ci代表购买积分、Wi代表京东价格、Mi代表库存
  27.      * @param goods 二维数组goods[1...n]：goods[i][0]、goods[i][1]、goods[i][2]表示每个商品的购买积分、京东价格、库存量
  28.      * @param totalScore 总积分
  29.      * @return choose[1...n]表示各物品的选择状态
  30.      */
  31.     public static int[] chooseGoods(int[][] goods, int totalScore){
  32.         // 三维数组maxValue[i][j][0]、maxValue[i][j][1]表示在前i种物品，j积分情况下选择到的最大价值与当前物品选择个数
  33.         int[][][] maxValue = new int[goods.length][totalScore+1][2];
  34.         for (int i = 1; i < goods.length; i++){
  35.             for (int j = 1; j < totalScore+1; j++){
  36.                 // 遍历第i种物品在积分为j时的所有购买个数，找出最大价值
  37.                 for (int k = 0; k <= goods[i][2]; k++){
  38.                     if (goods[i][0]*k>j){
  39.                         // 所需积分大于了当前总积分
  40.                         break;
  41.                     } else {
  42.                         // 当前可以选择k个物品
  43.                         int value = goods[i][1]*k+maxValue[i-1][j-goods[i][0]*k][0];
  44.                         if (maxValue[i][j][0] < value){
  45.                             // 记录最大价值与购买个数
  46.                             maxValue[i][j][0] = value;
  47.                             maxValue[i][j][1] = k;
  48.                         }
  49.                     }
  50.                 }
  51.             }
  52.         }
  53.         int[] choose = new int[goods.length];
  54.         int nowScore = totalScore;
  55.         for (int i = goods.length-1; i > 0; i--){
  56.             // 记录当前在nowScore下选择了多少个i号商品
  57.             choose[i] = maxValue[i][nowScore][1];
  58.             nowScore -= goods[i][0]*choose[i];
  59.         }
  60.         return choose;
  61.     }
  62.     public static void display(int[] choose){
  63.         for (int i = 1; i < choose.length; i++){
  64.             System.out.print(choose[i]+" ");
  65.         }
  66.         System.out.println();
  67.     }
  68. }