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