• 動態(tài)規(guī)劃算法核心思想：
  1.刻畫問題的最優(yōu)解的結(jié)構(gòu)特征
  2.遞歸定義最優(yōu)解的值
  3.自底向上的方式計算最優(yōu)解的值
  4.構(gòu)造問題的最優(yōu)解

• 背包問題
  給定n個重量為w1,w2,...,wn,價值為v1,v2,...,vn的物品和一個承重量為W的背包奠旺，
  求這些物品中最有價值的一個子集并且要能夠放進背包中酒唉。
  在這里我們先假設(shè)重量為整數(shù)
  
  
  解法推導(dǎo)：

1. 刻畫最優(yōu)解的結(jié)構(gòu)特征（最復(fù)雜的過程）：
   先考慮由前 i 個物品（1 <= i <= n) 定義的一個實例矮烹，物品的重量為w1,...wi，價值為v1,...,vi，而背包的承重量為j(1 <= j <= W)蒿褂。那么求前i個物品中最有價值且能夠放進背包中的一個子集這個問題就構(gòu)成了前面所述的問題的一個子問題潘拨。
   我們先設(shè)F(i,j)為此時這個子問題的最優(yōu)解,其返回值即為最大價值（那么我們要求的就是F(n,W)），通過求解F(i,j)來尋找F(i,j)與更小的子問題之間的遞推關(guān)系蹦魔。
   此時我們可以用到分治法的思想激率，將求解F(i,j)這個問題按照第i個物品是否在F(i,j)中劃分為兩個子問題：1）包括第i個物品時的最優(yōu)解 2）不包括第i個物品時的最優(yōu)解
   然后比較這兩個誰更 “優(yōu)秀” 一些，在這個問題中勿决，即為比較誰的價值總和更大一些乒躺。

• 情況一：包括第i個物品時，F(xiàn)(i,j) = F(i-1,j - wi) + vi
• 情況二：不包括第i個物品時低缩，F(xiàn)(i,j) = F(i-1,j)
  上述兩種情況的結(jié)論可以用反證法進行證明嘉冒。

2. 得到最優(yōu)解值的遞歸定義:

• 2.1： j - wi >= 0： F(i,j) = max(F(i-1,j) , F(i-1,j-wi)+vi)
• 2.2：j - wi < 0： F(i,j) = F(i-1,j)

3. 自底向上求解：

• 我們很容易得到如下的初始條件：
  表中最上面一行：3.1：F(0,j) = 0(0 <= j <= W)
  表中最靠左邊一列：3.2：F(i,0) = 0(0 <=i <=W)
  然后采用填表的方式得到后續(xù)每一項F(i,j)的值

4. 構(gòu)造問題的最優(yōu)解
   求得F(n,W)

實例：
對于承重為5的背包有：

根據(jù)以上信息和公式2.1，2.2咆繁，3.1讳推，3.2，我們得到如下的動態(tài)規(guī)劃表：

i-前i個物品中
j-背包的承重量

因此最優(yōu)解F(4,5)=37.讀者們可以自行應(yīng)用前文所述算法來體驗這個表的填表過程玩般，這樣就可以明白動態(tài)規(guī)劃自底向上解決背包問題的優(yōu)勢所在：即許多表格單元的數(shù)據(jù)無需重復(fù)計算银觅，當(dāng)數(shù)據(jù)量比較大的時候，如果沒有這張表坏为，直接使用自上向下遞歸的方法那么求解一個問題將會有許多重復(fù)計算的數(shù)據(jù)究驴。
下面給出利用動態(tài)規(guī)劃自底向上求解背包問題的過程回溯，以此來得到我們最優(yōu)解當(dāng)中到底放了那些物品進背包：（i匀伏，j）
（4纳胧，5） -> （3，3）->（2帘撰，3）-> （1跑慕，2）->（0，0）
由上述過程知道我們放入的物品以此為1摧找，2核行，4.

下面給出自底向上的動態(tài)規(guī)劃求解背包問題的源代碼：

/**
 * 背包問題
 * 給定n個重量為w1,w2,...,wn,價值為v1,v2,...,vn的物品和一個承重量為W的背包，
 * 求這些物品中最有價值的一個子集并且要能夠放進背包中蹬耘。
 * @author Conor Xu
 */
public class NapsackQuestion {
    private int[] weight;
    private double[] value;
    private int[] stuff;
    private int n = 0;
    private int w = 0;
    
    //麻袋可以裝下的總重量
    private int capacityOfSack;
    
    //用來存F(i,j)的結(jié)果
    //i:0~n,j:0~capacityOfSack
    private double[][] func;
    
    public NapsackQuestion(int[] weight,double[] value,int capacityOfWeight) {
         this.weight = weight;
         this.value = value;
         this.capacityOfSack = capacityOfWeight;
         //表格的橫向長度為承重量+1,縱向長度為物品總數(shù)+1（最上一行和最左邊一列都是0）
         func = new double[weight.length + 1][capacityOfWeight + 1];
         stuff = new int[weight.length];
    }
    
    /**
     * 
     * @param n 對前n個物品求解
     * @param w 背包最大承受重量為w
     * @return i=n,j=w時的最優(yōu)解
     */
    public double resolve1(int n,int w) {
        int k = 0;
        for(int i = 1;i <= n;i++) {
            for(int j = 1;j <= w;j++) {
                if(j - weight[i-1] < 0)
                    func[i][j] = func[i-1][j];
                else if(func[i-1][j-weight[i-1]] + value[i-1] <= func[i-1][j]) {
                    func[i][j] = func[i-1][j];
                }
                else {
                    func[i][j] = func[i-1][j-weight[i-1]] + value[i-1];
                }
            }
        }
        
        //n,w用于打印當(dāng)前解決方法的“路徑”芝雪，即裝入的物品的序列。
        this.n = n;
        this.w = w;
        return func[n][w];
    }
    public void printStuff() {
        int i = n;
        int j = w;
        int k = 0;
        while(i > 0 && j > 0) {
            if(func[i][j] == func[i-1][j]) {
                i--;
            }
            else {
                stuff[k++] = i;
                i--;
                j -= weight[i];
            }
        }
        while(k > 1) {
            System.out.print(stuff[--k] + "->");
        }
        if(stuff[0] != 0)
            System.out.println(stuff[0]);
        else {
            System.out.println("there is nothing in your sack");
        }
        
    }
    public static void main(String[] args) {
        int[] weight = {2,1,3,2};
        double[] value = {12,10,20,15};
        NapsackQuestion sackQues = new NapsackQuestion(weight,value,5);
        System.out.println(sackQues.resolve1(4,4));
        sackQues.printStuff();
    }
    

其中printstuff用于打印裝入背包的所有物品综苔。