Java實現(xiàn)動態(tài)規(guī)劃背包問題
前言
給定 n n n 種物品和一個背包。物品 i i i 的重量是 w i wi wi,其價值為 v i vi vi,背包的容量為 c c c。問應(yīng)如何選擇裝入背包的物品,使得裝入背包中物品的總價值最大?
一、原理
0 − 0 - 0− 1 1 1 背包問題是一個特殊的整數(shù)規(guī)劃問題。
1.1 最優(yōu)子結(jié)構(gòu)性質(zhì)
1.2 遞歸關(guān)系
設(shè)所給 0 − 1 0-1 0−1 背包問題的子問題的最優(yōu)值為 m(i,j),即 m(i,j)是背包容量為 j,可選擇物品為 i,i+1,…,n 時 0-1背包問題的最優(yōu)值。由 0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì),可以建立計算 m(i,j)的遞歸式如下:
二、算法描述
2.1 算法描述
偽代碼:
2.2 圖解
2.3 構(gòu)造最優(yōu)解
三、 0 − 1 0-1 0−1 背包問題相關(guān)題目
3.1 題目
已知有5個物體,它們的重量分別為:2,2,4,5,4,各物體的價值依次為6,3,5,4,6,背包大小為10,使用動態(tài)規(guī)劃法求矩陣m[i][j],并給出最優(yōu)解。修改數(shù)據(jù)為:5個物體,它們的重量分別為:1,1,2,3,2,各物體的價值依次為6,3,5,4,6,背包大小為6,使用動態(tài)規(guī)劃法求矩陣m[i][j],并給出最優(yōu)解
3.2 源程序(Java求解 0 − 1 0-1 0−1背包問題)
/** * 0-1背包問題(動態(tài)規(guī)劃法求解) */ public class E3_9 { //物品的個數(shù)+1(第一個數(shù)我寫成0) static int N = 6; //static int C = 7; static int C = 11; /** * 程序的入口 * @param args */ public static void main(String[] args) { //int n = N-1; //背包的容量 int c = C-1; int i; //物體的重量 //int w[] = new int[N]; int w[] = new int[]{0,2,2,4,5,4}; //int w[] = new int[]{0,1,1,2,3,2}; //物體的價值 //int v[] = new int[N]; int v[] = new int[]{0,6,3,5,4,6}; //動態(tài)規(guī)劃法求解過程的矩陣 int m[][] = new int[N][C]; //選擇的結(jié)果 int x[] = new int [N]; // for (i = 1; i < N; i++) { // w[i] = 1+(int) (Math.random()*5); // v[i] = 1+(int) (Math.random()*10); // } knapsack(v,w,c,m); traceback(m,w,c,x); System.out.printf("背包能裝的最大價值為:"+"%d \n ",m[1][c]); for (i = 1; i <= c; i++) { System.out.printf("%2d \t",i); } System.out.printf("重量 價值\n"); for (i = 1; i < N; i++) { System.out.printf("%d:",i); for (int j = 1; j <= c; j++) { System.out.printf("%2d \t",m[i][j]); } System.out.printf("%2d%4d\n",w[i],v[i]); } System.out.printf("\n\n物品的重量"); for (i = 1; i < N; i++) { System.out.printf("%2d \t",w[i]); } System.out.printf("\n物品的價值"); for (i = 1; i < N; i++) { System.out.printf("%2d \t",v[i]); } System.out.printf("\n選擇的結(jié)果"); for (i = 1; i < N; i++) { System.out.printf("%2d \t",x[i]); } System.out.printf("\n"); } /** * 由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立的遞歸式 * @param v 存儲物品價值的數(shù)組 * @param w 存儲物品重量的數(shù)組 * @param c 背包容量 * @param m 動態(tài)規(guī)劃法求解過程的矩陣 */ public static void knapsack(int []v,int []w,int c,int [][]m){ int n=v.length-1; int jMax=Math.min(w[n]-1,c); for(int j=0;j<=jMax;j++) m[n][j]=0; for(int j=w[n];j<=c;j++) m[n][j]=v[n]; for(int i=n-1;i>0;i--){ jMax=Math.min(w[i]-1,c); for(int j=0;j<=jMax;j++) m[i][j]=m[i+1][j]; for(int j=w[i];j<=c;j++) m[i][j]=Math.max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } //m[1][c]=m[2][c]; //對于i=1時的兩種情況 if(c>=w[1]) m[1][c]=Math.max(m[2][c],m[2][c-w[1]]+v[1]); else m[1][c]=m[2][c]; } /** * 構(gòu)造最優(yōu)解 * @param m 動態(tài)規(guī)劃法求解過程的矩陣 * @param w 存儲物體的重量的數(shù)組 * @param c 背包容量 * @param x 存儲選擇結(jié)果的數(shù)組 */ public static void traceback(int [][]m,int []w,int c,int []x){ int n=w.length-1; for(int i=1;i<n;i++) if(m[i][c]==m[i+1][c]) x[i]=0; else { x[i]=1; c-=w[i]; } x[n]=(m[n][c]>0)?1:0; } }
3.3 運行結(jié)果
總結(jié)
動態(tài)規(guī)劃基本步驟
- 找出最優(yōu)解的性質(zhì),并刻劃其結(jié)構(gòu)特征。
- 遞歸地定義最優(yōu)值。
- 以自底向上的方式計算出最優(yōu)值。
- 根據(jù)計算最優(yōu)值時得到的信息,構(gòu)造最優(yōu)解。
到此這篇關(guān)于Java實現(xiàn)動態(tài)規(guī)劃背包問題的文章就介紹到這了,更多相關(guān)java動態(tài)規(guī)劃內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
RestTemplate如何通過HTTP?Basic?Auth認證示例說明
這篇文章主要為大家介紹了RestTemplate如何通過HTTP?Basic?Auth認證的示例說明,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2022-03-03Java 獲取網(wǎng)絡(luò)302重定向URL的方法
在本篇文章里小編給大家整理的是關(guān)于Java 獲取網(wǎng)絡(luò)302重定向URL的方法以及相關(guān)知識點,有興趣的朋友們參考下。2019-08-08IDEA中啟動多個SpringBoot服務(wù)的實現(xiàn)示例
本文主要介紹了IDEA中啟動多個SpringBoot服務(wù)的實現(xiàn)示例,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-08-08從零構(gòu)建可視化jar包部署平臺JarManage教程
這篇文章主要為大家介紹了從零構(gòu)建可視化jar包部署平臺JarManage教程詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-05-05JavaWeb開發(fā)入門第二篇Tomcat服務(wù)器配置講解
JavaWeb開發(fā)入門第二篇主要介紹了Tomcat服務(wù)器配置的方法教大家如何使用Tomcat服務(wù)器,感興趣的小伙伴們可以參考一下2016-04-04spring boot整合RabbitMQ實例詳解(Fanout模式)
這篇文章主要介紹了spring boot整合RabbitMQ的實例講解(Fanout模式),非常不錯,具有參考借鑒價值,需要的朋友可以參考下2017-04-04詳解SpringBoot Redis自適應(yīng)配置(Cluster Standalone Sentinel)
這篇文章主要介紹了詳解SpringBoot Redis自適應(yīng)配置(Cluster Standalone Sentinel),文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-07-07MyEclipse2017創(chuàng)建Spring項目的方法
這篇文章主要為大家詳細介紹了MyEclipse2017創(chuàng)建Spring項目的方法,具有一定的參考價值,感興趣的小伙伴們可以參考一下2018-03-03