欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃背包問(wèn)題

 更新時(shí)間:2021年06月21日 17:03:25   作者:Abro.  
本文主要介紹使用java實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃的背包問(wèn)題,詳細(xì)使用圖文和多種案例進(jì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)文章

最新評(píng)論