第1章游戏之乐——买书问题

买书问题

1. 问题描述

　　上柜的《哈利波特》平装本系列，一共有五卷。假设每一卷单独销售均需8欧元。如果读者一次购买不同的两卷，就可以扣除5%的费用，三卷则更多。假设具体折扣的情况如下：

　　问题：要求根据这样的需求，设计出算法，能够计算出读者所购买一批书的最低价格。

2. 问题分析：

优化问题一般采用动态规划、贪心算法、分支限界这些思路进行，直到找到最优解！！

贪心策略

当书的数目N<5时，直接按照折扣购买

当书的数目N>5时，情况如下：

依此可以穷举出每一种组合的情况，对于任意一种情况(i,j,k,m,n)进行分析

先找出是所有书中5种不同的书，如果有则按照5本书折扣价购买

其次找出剩余书中所有4种书，如果有则按照4本书的折扣价购买

再找出剩余书中所有3种书，如果有则按照3本书的折扣价购买 

最后在剩余书中找出所有2种书，如果有则按照2本书的折扣价购买

剩下的书则按照全价购买。

如果按照这种方法（贪心法）存在反例，比如买8本书时，可以拆成5+3，折扣为1.55；也可以拆成4+4，折扣为1.6 这种两种情况组合中都包括，通过选择一个折扣最低的可以排除掉第一种情况。

结论：贪心策略不可取

动态规划

要用动态规划解答首先要找到，动态规划的递归公式，因为动态规划是自顶向下层层递归，然后自底向下层层解答！最后根据底层结论求解最后结果。

五卷书的价格相同都是8欧元，所以购买（1，0，0，0，0）跟（0，1，0，0，0）效果一样。这里就可以简化为，让所购买书按照本书递减（递增），从而方便讨论。

要处理的参数为购买每种卷的个数，所以递归一定跟这五个参数相关。可以把参数按照从小到大顺序排列。讨论不为0的参数的个数，从而求出所有可能的折扣种类。然后从当前折扣种类中取价格最小值。

（X1,X2,X3,X4,X5）代表购买每卷的个数，F（X1，X2，X3，X4，X5）代表最低价格。X1 >= X2 >= X3 >= X4 >= X5

F（X1，X2，X3，X4，X5）=0  ；当所有参数都为0的情况（这也是退出递归的出口）

F（X1，X2，X3，X4，X5）= min{

                           5*8*(1-25%) +F（X1-1，X2-1，X3-1，X4-1，X5-1）  //x5 >= 1

                           4*8*(1-20%) +F（X1-1，X2-1，X3-1，X4-1，X5）    //x4 >= 1

                           3*8*(1-10%) +F（X1-1，X2-1，X3-1，X4，X5）      //x3 >= 1

                           2*8*(1-5%) +F（X1-1，X2-1，X3，X4，X5）         //x2 >= 1

                           8 +F（X1-1，X2，X3，X4，X5）                    //x1 >= 1

                           }

3. 动态规划java源码：

package chapter1youxizhileBuybook;

import java.util.ArrayList;
import java.util.List;

/**
 * 买书问题
 * @author DELL
 *
 */
public class BuyBook1 {
    private double discount[];  //买书本数的折扣（从1本开始，增序排列）
    private double price;  //书的价格每本书都一样
    
    //构造函数
    public BuyBook1(double discount[],double price){
        this.discount = discount;
        this.price = price;
    }
    /**
     * 插入排序
     * 排序结果为从大到小
     * @param a
     */
    private void insertSort(int a[]){ 
        int temp,i,j;
        for(i=1;i<a.length;i++){
            temp = a[i];
            j=i-1;
            while((j>=0)&&(a[j]<temp)){
                a[j+1]=a[j];  //后移
                j--;
            }
            a[j+1]=temp;
        }
    }
    
    /**
     * 求数组中的最小值
     * @param a 求最小值的数组
     * @return 最小值
     */
    private double min(Double[] a){
        int i;
        double m;  //保存最小值
        m=a[0];  //默认第一个为最小值
        for(i=1;i<a.length;i++){
            if(a[i]<m)
                m=a[i];
        }
        return m;
    }
    
    /**
     * 根据买书卷数求最小价格
     * @param x1,x2,x3,x4,x5  买不同书卷数
     */
    public double minPrice(int x1,int x2, int x3, int x4, int x5){
        int i;
        int a[] = {x1,x2,x3,x4,x5};
        if(x1==0&&x2==0&&x3==0&&x4==0&&x5==0) 
            return 0;
        insertSort(a);
        List<Double> list = new ArrayList<Double>(); //用于存放各种情况的价格
        if(a[4]>=1){
            i=4;
            double x = (i+1)*price*(1-discount[i])+minPrice(a[0]-1,a[1]-1,a[2]-1,a[3]-1,a[4]-1);
            list.add(x);                
        }
        if(a[3]>=1){
            i=3;
            double x = (i+1)*price*(1-discount[i])+minPrice(a[0]-1,a[1]-1,a[2]-1,a[3]-1,a[4]);
            list.add(x);                
        }
        if(a[2]>=1){
            i=2;
            double x = (i+1)*price*(1-discount[i])+minPrice(a[0]-1,a[1]-1,a[2]-1,a[3],a[4]);
            list.add(x);                
        }
        if(a[1]>=1){
            i=1;
            double x = (i+1)*price*(1-discount[i])+minPrice(a[0]-1,a[1]-1,a[2],a[3],a[4]);
            list.add(x);                
        }
        if(a[0]>=1){
            i=0;
            double x = (i+1)*price*(1-discount[i])+minPrice(a[0]-1,a[1],a[2],a[3],a[4]);
            list.add(x);                
        }
        Double mv[];
        mv = new Double[list.size()];
        list.toArray(mv);    //将列表转换为数组
        return min(mv);  //返回最小值
    }
    public static void main(String[] args) {
//        int a[] = {2,2,2,1,1};  //买书卷数
        double discount[] = {0,0.05,0.1,0.2,0.25}; //折扣
        double price = 8;  //每本书的价格
        BuyBook1 book = new BuyBook1(discount,price);
        System.out.println("最低价格为："+book.minPrice(2,2,2,1,1));
    }

}

程序运行结果如下：

最低价格为：51.2