Java怎么實現(xiàn)背包動態(tài)規(guī)劃

本篇內(nèi)容主要講解“Java怎么實現(xiàn)背包動態(tài)規(guī)劃”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“Java怎么實現(xiàn)背包動態(tài)規(guī)劃”吧!

背包問題

【題目描述】
一個旅行者有一個最多能裝 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)轉移方程：

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]);

完整代碼如下：

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();
    }
}

當然，如果容量數(shù)字和物品個數(shù)很大的時候，這個表會很大，但是dp數(shù)組只與自己的上一次有關，會造成空間浪費，所以我們可以改進成滾動數(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怎么實現(xiàn)背包動態(tài)規(guī)劃”有了更深的了解，不妨來實際操作一番吧！這里是億速云網(wǎng)站，更多相關內(nèi)容可以進入相關頻道進行查詢，關注我們，繼續(xù)學習！