腳本之家服務(wù)器常用軟件

快捷導(dǎo)航

軟件下載

android MAC 驅(qū)動(dòng)下載字體下載 DLL

源碼下載

PHP ASP.NET ASP JSP

軟件編程

C# JAVA C 語言 Delphi Android

網(wǎng)絡(luò)編程

PHP ASP.NET ASP JavaScript

在線工具

CSS格式化 JS格式化 Html轉(zhuǎn)化為Js

數(shù)據(jù)庫

MYSQL MSSQL oracle DB2 MARIADB

CMS

PHPCMS DEDECMS 帝國CMS WordPress

常用工具

PHP開發(fā)工具 python Photoshop 必備軟件

Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之背包問題

更新時(shí)間：2022年02月18日 09:30:11 作者：我是小白呀

背包問題是一個(gè)非常典型的考察動(dòng)態(tài)規(guī)劃應(yīng)用的題目，對(duì)其加上不同的限制和條件，可以衍生出諸多變種，若要全面理解動(dòng)態(tài)規(guī)劃，就必須對(duì)背包問題了如指掌

概述

從今天開始, 小白我將帶大家開啟 Java 數(shù)據(jù)結(jié)構(gòu) & 算法的新篇章.

動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃 (Dynamic Programming) 的核心思想是把大問題劃分為小問題進(jìn)行解決. 先求解子問題, 然后從這些子問題的解得到原問題的解.

動(dòng)態(tài)規(guī)劃的優(yōu)點(diǎn):

可以幫助我們解決多階段問題, 化繁為簡(jiǎn)

動(dòng)態(tài)規(guī)劃的缺點(diǎn):

沒有統(tǒng)一的處理方法, 具體問題具體分析
當(dāng)變量的維數(shù)增大時(shí), 計(jì)算和存儲(chǔ)會(huì)急劇增大

背包問題

背包問題 (Knapsack Problem) 指有 N 件物品和一個(gè)容量為 V 的背包. 第 i 件物品的費(fèi)用是 c[i]，價(jià)值是 w[i]. 求解將哪些物品裝入背包可使價(jià)值總和最大.

代碼實(shí)現(xiàn)

public class 背包問題 {

    public static void main(String[] args) {

        int[] w = {1, 2, 3};  // 物品重量
        int[] val = {6, 10, 12};  // 物品價(jià)值
        int m = 5;  // 背包容量
        int n = val.length;  //

        // 創(chuàng)建二維數(shù)組
        int[][] v = new int[n + 1][m + 1];

        // 將第一行和第一列賦值為0
        for (int i = 0; i < v.length; i++) {
            v[i][0] = 0;
        }

        for (int i = 0; i < v[0].length; i++) {
            v[0][i] = 0;
        }

        // 動(dòng)態(tài)處理
        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[0].length; j++) {


                if (w[i - 1] > j) {
                    // 不裝入背包
                    v[i][j] = v[i - 1][j];
                } else {
                    // 裝入背包
                    v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
                }
            }
        }

        // 輸出二維數(shù)組
        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[0].length; j++) {
                System.out.print(v[i][j] + "\t");
            }
            System.out.println();
        }
    }
}

輸出結(jié)果: