淺析背包問(wèn)題動(dòng)態(tài)規(guī)劃 Java語(yǔ)言實(shí)現(xiàn)

背包問(wèn)題是非常經(jīng)典的動(dòng)態(tài)規(guī)劃問(wèn)題，其存在的歷史可追溯至19世紀(jì)末。本文將和大家分享一下，使用 Java 語(yǔ)言來(lái)解決背包問(wèn)題。以下是詳情內(nèi)容。

背包問(wèn)題

【題目描述】
一個(gè)旅行者有一個(gè)最多能裝 MM 公斤的背包，現(xiàn)在有 nn 件物品，它們的重量分別是W1，W2，…,WnW1，W2，…,Wn,它們的價(jià)值分別為C1,C2,…,CnC1,C2,…,Cn，求旅行者能獲得最大總價(jià)值。

【輸入】
第一行：兩個(gè)整數(shù)，MM(背包容量，M<=200M<=200)和NN(物品數(shù)量，N<=30N<=30)；

第2…N+12…N+1行：每行二個(gè)整數(shù)Wi，CiWi，Ci，表示每個(gè)物品的重量和價(jià)值。

【輸出】
僅一行，一個(gè)數(shù)，表示最大總價(jià)值。

【輸入樣例】
10 4
2 1
3 3
4 5
7 9
【輸出樣例】
12

我們可以通過(guò)自己打表的方式找變化求得狀態(tài)方程
（橫向表示容量，j）(縱向表示第幾個(gè)，i)
#1 2 3 4 5 6 7 8 9 10
1 0 1 1 1 1 1 1 1 1 1
2 0 1 3 3 4 4 4 4 4 4
3 0 1 3 5 5 6 8 8 9 9
4 0 1 3 5 5 6 9 9 10 12

dp[i][j]----i表示物品個(gè)數(shù)，j表示容量，dp[i][j]的值表示在此狀態(tài)的最大價(jià)值
由此我們可以寫(xiě)出狀態(tài)轉(zhuǎn)移方程：

if(j<w[i])//當(dāng)容量小于重量，即不拿的情況下
	dp[i][j]=dp[i-1][j]//等于上一次的值
else
	 dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);

完整代碼如下：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m, n;
        int[] w = new int[35];
        int[] v = new int[35];
        m = in.nextInt();
        n = in.nextInt();
        int[][] dp = new int[35][205];//m容量，n數(shù)目個(gè)數(shù)

        for (int i = 1; i <= n; i++) {
            w[i] = in.nextInt();
            v[i] = in.nextInt();
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if(j<w[i])
                {
                    dp[i][j]=dp[i-1][j];
                }else
                {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
                }
            }
        }
        //輸出dp數(shù)組
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println(dp[n][m]);
        in.close();
    }
}

當(dāng)然，如果容量數(shù)字和物品個(gè)數(shù)很大的時(shí)候，這個(gè)表會(huì)很大，但是dp數(shù)組只與自己的上一次有關(guān)，會(huì)造成空間浪費(fèi)，所以我們可以改進(jìn)成滾動(dòng)數(shù)組，減小空間，使其變成一維數(shù)組。

小tips：因?yàn)槭菨L動(dòng)數(shù)組，所以如果第二層循環(huán)從1開(kāi)始的話，可能會(huì)覆蓋上一次的值，所以第二層循環(huán)的時(shí)候我們從后往前開(kāi)始！

import java.util.*;
import java.lang.*;

public class Main {
    static int[]dp=new int[205];
    static int[] w = new int[35];
    static int[] v = new int[35];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m, n;
        m = in.nextInt();
        n = in.nextInt();
//        int[][] dp = new int[35][205];//m容量，n數(shù)目個(gè)數(shù)


        for (int i = 1; i <= n; i++) {
            w[i] = in.nextInt();
            v[i] = in.nextInt();
        }

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

        }
        //輸出dp數(shù)組
//        for (int i = 1; i <= n; i++) {
//            for (int j = 1; j <= m; j++) {
//                System.out.print(dp[i][j]+" ");
//            }
//            System.out.println();
//        }
//        System.out.println(dp[n][m]);
        System.out.println(dp[m]);
        in.close();
    }
}

以上就是使用 Java 語(yǔ)言解決背包問(wèn)題的詳細(xì)內(nèi)容，想要了解更多關(guān)于 Java 動(dòng)態(tài)規(guī)劃背包以及其他的資料請(qǐng)關(guān)注W3Cschool其它相關(guān)文章！