【动态规划】一个巧妙的买书问题给大家探讨。【java吧】

01月11日漏签0天

java吧关注：1,237,732贴子：12,708,105

3回复贴，共1页

<返回java吧

【动态规划】一个巧妙的买书问题给大家探讨。

只看楼主收藏回复

《编程之美》1.4节。

动态规划函数式：
(当Y1=Y1=Y3=Y4=Y5=0)时 F(Y1,Y2,Y3,Y4,Y5)=0
F(Y1,Y2,Y3,Y4,Y5) = min{
5*8*(1-0.25) +F(Y1-1,Y2-1,Y3-1,Y4-1,Y5-1) (Y5>0)
4*8*(1-0.20)+F(Y1-1,Y2-1,Y3-1,Y4-1,Y5) (Y4>0)
3*8*(1-0.10)+F(Y1-1,Y2-1,Y3-1,Y4,Y5) (Y3>0)
2*8*(1-0.05)+F(Y1-1,Y2-1,Y3,Y4,Y5) (Y2>0)
F(Y1-1,Y2,Y3,Y4,Y5) (Y1>0)
}
空间和时间复杂度都为O（Y1*Y2*Y3*Y4*Y5）
此题一看到动态规划函数式，发现不难。但是做过动态规划的同学们，都知道在空间复杂度为O（X*Y）的时候用到二维数组，0-1背包问题就是。
但是这个空间复杂度初一看上去，特么的，这是什么？5维数组？呵呵哒。
所以此题我用了一个较为巧妙的方法，不是动态规划的自底向上，是自顶向下备忘录法。
备忘录是用HashMap做的。
key为String "Y1-Y2-Y3-Y4-Y5";
个人认为较为巧妙，如果有更好的数据结构，欢迎吊打我。

送TA礼物

1楼2015-04-18 00:57回复

package chapter1;
import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/**
* 1.4 BuyBook问题
* @author hadoop
*
*/
public class Buybook {
static class Book{
public static final int PRICE = 8;
static Map<String, Double> bookmap = new HashMap<String, Double>();
static double[] perference = new double[5];
static{
bookmap.put("0-0-0-0-0-", Double.valueOf(0));
perference[4]=0;
perference[3]=0.05;
perference[2]=0.1;
perference[1]=0.2;
perference[0]=0.25;
}
int chapter;
}
public static int[] dealBookArr(int[] book,int i){
int[] copy =Arrays.copyOf(book, book.length);
for(int j=i;j<copy.length;j++){
if(copy[j]>0){
copy[j] = book[j] -1;
}
}
Arrays.sort(copy);
return copy;
}
public static double dpSort(int[] book){
String key = getKey(book);
Double value = Book.bookmap.get(key);
if(value!=null){
return value;
}
double[] arr = new double[5];
for(int i=0;i<book.length;i++){
if(book[i]>0){
int[] copy = dealBookArr(book, i);
arr[i] =(5-i)*8*Book.perference[i]+dpSort(copy);
}
}
Arrays.sort(arr);
value = arr[4];
Book.bookmap.put(key, value);
return value;
}
public static String getKey(int... args){
StringBuilder sb = new StringBuilder();
for(int i :args){
sb.append(i+"-");
}
return sb.toString();
}
public static void main(String[] args) {
int[] book = {2,2,4,4,4};
double a = dpSort(book);
DecimalFormat df=new DecimalFormat("#.00");
System.out.println(df.format(a));
}
}

2楼2015-04-18 00:57