??"Su7"??
作者：Lvzi
文章主要內(nèi)容：算法系列–動態(tài)規(guī)劃–背包問題(3)–完全背包介紹

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

一.完全背包問題

鏈接:
完全背包

可以發(fā)現(xiàn)完全背包問題和01背包問題還是特比相似的

分析:

完全背包問題是01背包問題的推廣,是以01背包問題為基礎(chǔ),兩種問題的狀態(tài)表示是相同的

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

分析狀態(tài)轉(zhuǎn)移方程時也是以最后一個位置的狀態(tài)去劃分,分為選/不選nums[i],此處就體現(xiàn)出完全背包問題和01背包問題最大的差別,01背包問題如果選擇nums[i],選擇的物品的數(shù)量只能是1(+w[i]),但是完全背包問題如果選擇nums[i],可以選擇的數(shù)量是任意多個(+n * w[i]),此時的狀態(tài)是任意多個,這樣的狀態(tài)我們在正則表達(dá)式匹配那道問題中已經(jīng)遇到過,解決思路就是利用數(shù)學(xué)規(guī)律,將任意多個狀態(tài)使用簡單的幾個狀態(tài)表示,具體操作是觀察所有狀態(tài)中不變的量,大膽假設(shè),小心求證!!!

以下是狀態(tài)轉(zhuǎn)移方程的推導(dǎo):

• dp[i][j] = Max(dp[i-1][j],dp[i][j - nums[i]] + w[i])

初始化

• 根據(jù)狀態(tài)表示分析出不需要初始化

返回值:

• dp[n][V]

代碼:

import java.util.Scanner;

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

        int[] v = new int[n + 1], w = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            v[i] = in.nextInt();// 物品體積
            w[i] = in.nextInt();// 物品價值
        }

        int[][] dp = new int[n + 1][V + 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][j] = Math.max(dp[i][j],dp[i][j - v[i]] + w[i]);
            }
        }

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

        // 1.解決第二問
        dp = new int[n + 1][ V + 1];// 好的代碼風(fēng)格?
        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][j - v[i]] != -1)
                    dp[i][j] = Math.max(dp[i][j],dp[i][j - v[i]] + w[i]);
            }
        }
        System.out.println(dp[n][V] == -1 ? 0 : dp[n][V]);
    }
}

空間優(yōu)化:
同樣的在完全背包問題中也可以進(jìn)行空間優(yōu)化(想想01背包問題中的空間優(yōu)化,通過明確遍歷順序,只是用一個簡單的線性數(shù)組就可以完成填表)

01背包問題的空間優(yōu)化最需要注意的就是遍歷順序的改變,在01背包問題中,為了在填表的時候需要使用的數(shù)據(jù)不被覆蓋掉,需要從右往左遍歷,但是在完全背包問題中,需要從左往右遍歷

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

import java.util.Scanner;

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

        int[] v = new int[n + 1], w = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            v[i] = in.nextInt();// 物品體積
            w[i] = in.nextInt();// 物品價值
        }

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

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

        // 2.解決第二問
        dp = new int[ V + 1];// 好的代碼風(fēng)格?
        for(int j = 1; j <= V; j++) dp[j] = -1;
        for(int i = 1; i <= n; i++)
            for(int j = v[i]; j <= V; j++)
                if(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]);
    }
}

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

到了這里，關(guān)于算法系列--動態(tài)規(guī)劃--背包問題(3)--完全背包介紹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！