??"趁著年輕,做一些比較cool的事情"??
作者：Lvzi
文章主要內(nèi)容：算法系列–動(dòng)態(tài)規(guī)劃–背包問題(1)–01背包介紹

大家好,今天為大家?guī)淼氖?code>算法系列--動(dòng)態(tài)規(guī)劃--背包問題(1)--01背包介紹

一.什么是背包問題

背包問題是動(dòng)態(tài)規(guī)劃中經(jīng)典的一類問題,經(jīng)常在筆試面試中出現(xiàn),是非常具有區(qū)分度的題目

背包問題的種類很多,變式多,也就使得背包問題的難度一般都很高,而01背包問題屬于其中最基礎(chǔ),可以當(dāng)做思考模版的題目,下面就來講解–01背包問題

前情提示:如果你沒有動(dòng)態(tài)規(guī)劃的基礎(chǔ),還是盡量不要通過背包問題入門,先去做上幾十到動(dòng)態(tài)規(guī)劃的題目再來學(xué)習(xí)背包問題

二.01背包問題

鏈接:
01背包問題

分析:

首先要明確這道題目一共有兩問,第一問求的是在不超過背包限制的前提下,可以得到的最大價(jià)值
,第二問求的是在剛好裝滿背包的情況下,可以得到的最大價(jià)值

第一問:求這個(gè)背包至多能裝多大價(jià)值的物品？

我們先來模擬一下背包問題的執(zhí)行過程,其實(shí)就是從所有物品中選擇合適的物品填入背包,來實(shí)現(xiàn)價(jià)值的最大化,在選物品時(shí)我們是可以任意選擇的,這不就類似于在任意的子序列中,選出最大xxxx的問題么?

好了,相信大家也能分析到這里,說:這不就是一個(gè)簡(jiǎn)單的子序列問題么,這有啥難得,于是興致勃勃的寫下狀態(tài)表示

• dp[i]:表示在[1,i]之間的所有物品中,可以實(shí)現(xiàn)的最大價(jià)值物品的價(jià)值

(注:下標(biāo)我們從1開始是因?yàn)檫@是dp問題常用的一種初始化dp表的方式)

但是我們?cè)谔?code>i位置的值時(shí),需要考慮此時(shí)背包容量對(duì)我們裝填的影響(比如如果背包的容量很小,只有1,而我們i物品的體積是99,肯定無法裝進(jìn)去)

所以我們還需要一個(gè)狀態(tài)來表示背包體積,也就是每走到一個(gè)物品都要保證符合容量大小,于是狀態(tài)表示如下:

• dp[i][j]:在[1,i]之間的所有物品中,體積不超過j,可以實(shí)現(xiàn)的最大價(jià)值物品的價(jià)值

我們可以驗(yàn)證一下這個(gè)狀態(tài)表示能否返回最終的結(jié)果呢?可以,dp[n][V]就表示在所給定的n個(gè)物品中,體積不超過背包的最大體積V,選擇可以實(shí)現(xiàn)最大價(jià)值的物品的價(jià)值

接下來就來推到狀態(tài)轉(zhuǎn)移方程:

狀態(tài)轉(zhuǎn)移方程一般就是根據(jù)最后一個(gè)位置的狀態(tài)去討論,在本題中,分類討論的依據(jù)就是包不包括最后一個(gè)物品

注意:選nums[i]這種情況不是一定能實(shí)現(xiàn)的,需要滿足此時(shí)的背包體積大于第i個(gè)物品的體積,也就是需要滿足j - v[i] >= 0

返回值:dp[n][V]
以上就是第一問的詳細(xì)分析過程

第二問:若背包恰好裝滿，求至多能裝多大價(jià)值的物品？

相較于第一問多了體積的限制,必須要滿足體積的前提下實(shí)現(xiàn)價(jià)值的最大化,但是大致的思路和第一問很像,只需要在第一問的基礎(chǔ)上做出一些改變即可:

• dp[i][j]:表示在[0,i]區(qū)間內(nèi)的物品,在體積為j的前提下,可以實(shí)現(xiàn)的最大價(jià)值

狀態(tài)轉(zhuǎn)移方程

這里多了個(gè)限制條件dp[i - 1][j - v[i]] != -1,還是根據(jù)題目要求得來的,要考慮一種特殊情況,也就是在[0,i]區(qū)間內(nèi)的物品根本無法組合成體積為j的情況(這也是會(huì)存在的),要想i位置存在價(jià)值,必須保證i-1位置剛好能夠?qū)崿F(xiàn)j-v[i]的體積

初始化相較于第一問也有所不同,具體來說需要把dp表的第一行初始化為-1(除了dp[0][0]),第一行代表不選擇任何物品,也就無法構(gòu)成滿足j體積這個(gè)條件,我們將其設(shè)置為-1

之所以設(shè)置為-1是為了和dp[0][0] = 0這種情況作區(qū)分

代碼:

import java.util.Scanner;

// 注意類名必須為 Main, 不要有任何 package xxx 信息
public class Main {
    static int N = 1010;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), V = in.nextInt();// 獲取物品數(shù)目和背包體積

        // 處理第一問
        int[] v = new int[N],w = new int[N];// 存儲(chǔ)物品的體積和價(jià)值
        for(int i = 1; i <= n; i++) {// 輸入數(shù)值
            v[i] = in.nextInt(); 
            w[i] = in.nextInt();
        }

        int[][] dp = new int[N][N];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= V; j++) {
                dp[i][j] = dp[i - 1][j];
                if(j - v[i] >= 0) 
                    dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - v[i]] + w[i]);
            }
        }

        System.out.println(dp[n][V]);

        // 處理第二問
        dp = new int[N][N];
        for(int j = 1; j <= V; j++) {// 初始化
            dp[0][j] = -1;
        }

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= V; j++) {
                dp[i][j] = dp[i - 1][j];
                if(j - v[i] >= 0 && dp[i - 1][j - v[i]] != -1)
                    dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - v[i]] + w[i]);
            }
        }
        System.out.println(dp[n][V] == -1 ? 0 : dp[n][V]);
    }
}

上述解法的空間復(fù)雜度是很高的,我們開辟的dp表是一個(gè)N*N的,下面介紹使用滾動(dòng)數(shù)組實(shí)現(xiàn)空間優(yōu)化

空間優(yōu)化之后的代碼:

import java.util.Scanner;

// 注意類名必須為 Main, 不要有任何 package xxx 信息
public class Main {
    static int N = 1010;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), V = in.nextInt();// 獲取物品數(shù)目和背包體積

        // 處理第一問
        int[] v = new int[N],w = new int[N];// 存儲(chǔ)物品的體積和價(jià)值
        for(int i = 1; i <= n; i++) {// 輸入數(shù)值
            v[i] = in.nextInt(); 
            w[i] = in.nextInt();
        }

        int[] dp = new int[N];
        for(int i = 1; i <= n; i++) 
            for(int j = V; j >= v[i]; j--) 
                dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]);
            
        System.out.println(dp[V]);

        // 處理第二問
        dp = new int[N];
        for(int j = 1; j <= V; j++) 
            dp[j] = -1;// 初始化

        for(int i = 1; i <= n; i++) 
            for(int j = V; j >= v[i]; j--) 
                if(j - v[i] >= 0 && dp[j - v[i]] != -1)
                    dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]);
              
        System.out.println(dp[V] == -1 ? 0 : dp[V]);
    }
}

總結(jié):本文的核心要點(diǎn)

1. 什么是背包問題
2. 01背包問題詳解
3. 背包問題的空間優(yōu)化(滾動(dòng)數(shù)組)

以上就是算法系列--動(dòng)態(tài)規(guī)劃--背包問題(1)--01背包介紹全部?jī)?nèi)容,下一篇文章將會(huì)帶來01背包問題的拓展題目,敬請(qǐng)期待,我是LvZi文章來源地址http://www.zghlxwxcb.cn/news/detail-853300.html

到了這里，關(guān)于算法系列--動(dòng)態(tài)規(guī)劃--背包問題(1)--01背包介紹的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！