背包問題主要是指一個給定容量的背包、若干具有一定價值和重量的物品，如何選擇物品放入背包使物品的價值大。其中又分01背包和無限背包，這里主要討論01背包，即每個物品最多放一個。而無限背包可以轉(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è)人才，有力地推動了成百上千企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。

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

好的，我們的算法就是基于此三個結(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}; //物品價值 
    int m = 12; //背包容量 
    int n = val.length; //物品個數(shù) 
    int[][] f = new int[n+1][m+1]; //f[i][j]表示前i個物品能裝入容量為j的背包中的大價值 
    int[][] path = new int[n+1][m+1]; 
    //初始化第一列和第一行 
    for(int i=0;ij) 
          f[i][j] = f[i-1][j]; 
        else{ 
          if(f[i-1][j]0&&j>0){ 
      if(path[i][j] == 1){ 
        System.out.print("第"+i+"個物品裝入 "); 
        j -= weight[i-1]; 
      } 
      i--; 
    } 
  } 
} 

網(wǎng)頁名稱：Java背包問題求解實例代碼-創(chuàng)新互聯(lián)
轉(zhuǎn)載來于：http://weahome.cn/article/dijpep.html