背包問題主要是指一個(gè)給定容量的背包、若干具有一定價(jià)值和重量的物品，如何選擇物品放入背包使物品的價(jià)值大。其中又分01背包和無限背包，這里主要討論01背包，即每個(gè)物品最多放一個(gè)。而無限背包可以轉(zhuǎn)化為01背包。

專注于為中小企業(yè)提供成都做網(wǎng)站、成都網(wǎng)站建設(shè)服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)山陽免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動(dòng)了成百上千企業(yè)的穩(wěn)健成長(zhǎng)，幫助中小企業(yè)通過網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。

先說一下算法的主要思想，利用動(dòng)態(tài)規(guī)劃來解決。每次遍歷到的第i個(gè)物品，根據(jù)w[i]和v[i]來確定是否需要將該物品放入背包中。即對(duì)于給定的n個(gè)物品，設(shè)v[i]、w[i]分別為第i個(gè)物品的價(jià)值和重量，C為背包的容量。再令v[i][j]表示在前i個(gè)物品中能夠裝入容量為j的背包中的大價(jià)值。則我們有下面的結(jié)果：

（2），v[i][j]=v[i-1][j] 當(dāng)w[i]>j
（3），v[i][j]=max{v[i-1][j],v[i-1][j-w[i]]+v[i]} 當(dāng)j>=w[i]

好的，我們的算法就是基于此三個(gè)結(jié)論式。

一、01背包：

1、二維數(shù)組法

public class sf { 
  public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    int[] weight = {3,5,2,6,4}; //物品重量 
    int[] val = {4,4,3,5,3}; //物品價(jià)值 
    int m = 12; //背包容量 
    int n = val.length; //物品個(gè)數(shù) 
    int[][] f = new int[n+1][m+1]; //f[i][j]表示前i個(gè)物品能裝入容量為j的背包中的大價(jià)值 
    int[][] path = new int[n+1][m+1]; 
    //初始化第一列和第一行 
    for(int i=0;i<f.length;i++){ 
      f[i][0] = 0; 
    } 
    for(int i=0;i<f[0].length;i++){ 
      f[0][i] = 0; 
    } 
    //通過公式迭代計(jì)算 
    for(int i=1;i<f.length;i++){ 
      for(int j=1;j<f[0].length;j++){ 
        if(weight[i-1]>j) 
          f[i][j] = f[i-1][j]; 
        else{ 
          if(f[i-1][j]<f[i-1][j-weight[i-1]]+val[i-1]){ 
            f[i][j] = f[i-1][j-weight[i-1]]+val[i-1]; 
            path[i][j] = 1; 
          }else{ 
            f[i][j] = f[i-1][j]; 
          } 
          //f[i][j] = Math.max(f[i-1][j], f[i-1][j-weight[i-1]]+val[i-1]); 
        } 
      } 
    } 
    for(int i=0;i<f.length;i++){ 
      for(int j=0;j<f[0].length;j++){ 
        System.out.print(f[i][j]+" "); 
      } 
      System.out.println(); 
    } 
    int i=f.length-1; 
    int j=f[0].length-1; 
    while(i>0&&j>0){ 
      if(path[i][j] == 1){ 
        System.out.print("第"+i+"個(gè)物品裝入 "); 
        j -= weight[i-1]; 
      } 
      i--; 
    } 
  } 
} 

當(dāng)前文章：Java背包問題求解實(shí)例代碼-創(chuàng)新互聯(lián)
瀏覽路徑：http://jinyejixie.com/article48/dijpep.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站排名、網(wǎng)站設(shè)計(jì)、面包屑導(dǎo)航、網(wǎng)站改版、網(wǎng)站收錄、建站公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)