淺析背包問題動態(tài)規(guī)劃 Java語言實現(xiàn)

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

背包問題

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

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

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

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

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

我們可以通過自己打表的方式找變化求得狀態(tài)方程
（橫向表示容量，j）(縱向表示第幾個，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表示物品個數(shù)，j表示容量，dp[i][j]的值表示在此狀態(tài)的最大價值
由此我們可以寫出狀態(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ù)目個數(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ù)字和物品個數(shù)很大的時候，這個表會很大，但是dp數(shù)組只與自己的上一次有關(guān)，會造成空間浪費，所以我們可以改進成滾動數(shù)組，減小空間，使其變成一維數(shù)組。

小tips：因為是滾動數(shù)組，所以如果第二層循環(huán)從1開始的話，可能會覆蓋上一次的值，所以第二層循環(huán)的時候我們從后往前開始！

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ù)目個數(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 語言解決背包問題的詳細內(nèi)容，想要了解更多關(guān)于 Java 動態(tài)規(guī)劃背包以及其他的資料請關(guān)注W3Cschool其它相關(guān)文章！