1、問(wèn)題描述：

一個(gè)旅行者有一個(gè)最多能裝m公斤的背包，現(xiàn)在有n中物品，每件的重量分別是W1、W2、……、Wn，每件物品的價(jià)值分別為C1、C2、……、Cn， 需要將物品放入背包中，要怎么樣放才能保證背包中物品的總價(jià)值最大？

2、動(dòng)態(tài)規(guī)劃算法的概述

1）動(dòng)態(tài)規(guī)劃(Dynamic Programming)算法的核心思想是：將大問(wèn)題劃分為小問(wèn)題進(jìn)行解決，從而一步步獲取最優(yōu)解的處理算法

2）動(dòng)態(tài)規(guī)劃算法與分治算法類(lèi)似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。

3）與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題，經(jīng)分解得到子問(wèn)題往往不是互相獨(dú)立的。 ( 即下一個(gè)子階段的求解是建立在上一個(gè)子階段的解的基礎(chǔ)上，進(jìn)行進(jìn)一步的求解 )

4）動(dòng)態(tài)規(guī)劃可以通過(guò)填表的方式來(lái)逐步推進(jìn)，得到最優(yōu)解

3、解題思路

利用動(dòng)態(tài)規(guī)劃來(lái)解決，每次遍歷到的第i個(gè)物品，根據(jù) w[i]和v[i]來(lái)確定是否需要將該物品放入背包中。

對(duì)于給定的n個(gè)物品，

v[i]:第i個(gè)物品的價(jià)值

w[i]:第i個(gè)物品的重量

c:為背包的容量

v[i][j]表示在前i個(gè)物品中能夠裝入容量為j的背包中的最大價(jià)值。

1）v[i][0]=v[0][j]=0，表示第一行和第一列是0。

2）當(dāng)w[i]>j時(shí)：v[i][j]=v[i-1][j] ，當(dāng)準(zhǔn)備加入新增的物品的容量大于當(dāng)前背包的容量時(shí)，就直接使用上一個(gè)單元格的裝入

3）當(dāng)j>=w[i]時(shí)：v[i][j]=max{v[i-1][j] ,v[i]+v[i-1][j-w[i]]}，當(dāng)準(zhǔn)備加入的新增的物品的容量小于等于當(dāng)前背包的容量。

其中：

v[i-1][j]：就是上一個(gè)單元格的裝入的最大值

v[i]：表示當(dāng)前物品的價(jià)值

v[i-1][j-w[i]]：裝入i-1物品，到剩余空間j-w[i]的最大值

---

4、完整代碼及運(yùn)行結(jié)果

package com.example.demo;

public class DynamicProgramming {
    public static void main(String[] args) {
        //物品的重量
        int[] c = {7, 2, 6, 3, 5};
        //物品的價(jià)值
        int[] w = {21, 18, 9, 15, 6};
        //物品的個(gè)數(shù)
        int n = w.length;
        //背包的容量
        int v = 14;

        knapsackDP(c, w, n, v);

    }


    /**
     *利用動(dòng)態(tài)規(guī)劃來(lái)解決:
     * 每次遍歷到的第i個(gè)物品，根據(jù) w[i]和v[i]來(lái)確定是否需要將該物品放入背包中。
     * 對(duì)于給定的n個(gè)物品，
     * v[i]:第i個(gè)物品的價(jià)值
     * w[j]:第i個(gè)物品的重量
     * c:為背包的容量
     * v[i][j]表示在前i個(gè)物品中能夠裝入容量為j的背包中的最大價(jià)值。
     *
     * @param w   物品的重量
     * @param val 物品的價(jià)值
     * @param n   物品的個(gè)數(shù)
     * @param m   背包的容量
     * @return
     */
    public static int knapsackDP(int[] w, int[] val, int n, int m) {
        //v[i][j] 表示在前i個(gè)物品中能夠裝入容量為j的背包中的最大價(jià)值
        int[][] v = new int[n + 1][m + 1];
        //記錄放入物品的情況
        int[][] records = new int[n + 1][m + 1];

        //初始化第一行和第一列為0
        for (int i = 0; i < v.length; i++) {
            v[i][0] = 0;
        }
        for (int i = 0; i < v[0].length; i++) {
            v[0][i] = 0;
        }

        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[0].length; j++) {
                //當(dāng)w[i]>j時(shí),數(shù)組下標(biāo)從1開(kāi)始，所以-1
                if (w[i - 1] > j) {
                    v[i][j] = v[i - 1][j];
                } else {//當(dāng)j>=w[i]時(shí),數(shù)組下標(biāo)從1開(kāi)始，所以-1
                    if (v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
                        v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
                        //記錄
                        records[i][j] = 1;
                    } else {
                        v[i][j] = v[i - 1][j];
                    }

                }
            }
        }

        //
        for (int i = 0; i < v.length; i++) {
            for (int j = 0; j < v[i].length; j++) {
                System.out.print(v[i][j] + " ");
            }
            System.out.println();
        }

        System.out.println("============================");
        //行的最大下標(biāo)
        int i = records.length - 1;
        //列的最大下標(biāo)
        int j = records[0].length - 1;
        while (i > 0 && j > 0) { //從records的最后開(kāi)始找
            if (records[i][j] == 1) {
                System.out.printf("第%d個(gè)物品放入到背包\n", i);
                j -= w[i - 1]; //w[i-1]
            }
            i--;
        }
        return 0;
    }
}

程序運(yùn)行結(jié)果：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-406851.html