背包問題java,背包問題算法

本文目錄一覽：

• 1、背包問題算法java實現
• 2、0-1背包問題java代碼
• 3、_’ title=’回溯法解決0-1背包問題 java寫的 求大神指點~~~~(>_’>回溯法解決0-1背包問題 java寫的 求大神指點~~~~(>_
• 4、java語言，背包問題，從Excel表中讀取數據
• 5、01背包問題變種：從給定的N個正數中選取若干個數之和最接近M的JAVA寫法
• 6、java寫背包問題沒看懂

背包問題算法java實現

任何語言都是一樣的，貪心算法，先按價值除重量排序，一個一個的加到背包里，當超過背包允許的重量後，去掉最後加進去一個，跳過這一個以後再加後面的，如果還是超重，再跳過這個，一直到價值最大化位置。

0-1背包問題java代碼

import java.io.BufferedInputStream;

import java.util.Scanner;

public class test {

    public static int[] weight = new int[101];

    public static int[] value = new int[101];

    public static void main(String[] args) {

        Scanner cin = new Scanner(new BufferedInputStream(System.in));

        int n = cin.nextInt();

        int W = cin.nextInt();

        for (int i = 0; i  n; ++i) {

            weight[i] = cin.nextInt();

            value[i] = cin.nextInt();

        }

        cin.close();

        System.out.println(solve(0, W, n)); // 普通遞歸

        System.out.println(“=========”);

        System.out.println(solve2(weight, value, W)); // 動態規劃表

    }

    public static int solve(int i, int W, int n) {

        int res;

        if (i == n) {

            res = 0;

        } else if (W  weight[i]) {

            res = solve(i + 1, W, n);

        } else {

            res = Math.max(solve(i + 1, W, n), solve(i + 1, W – weight[i], n) + value[i]);

        }

        return res;

    }

    public static int solve2(int[] weight, int[] value, int W) {

        int[][] dp = new int[weight.length + 1][W + 1];

        for (int i = weight.length – 1; i = 0; –i) {

            for (int j = W; j = 0; –j) {

                dp[i][j] = dp[i + 1][j]; // 從右下往左上，i+1就是剛剛記憶過的背包裝到i+1重量時的最大價值

                if (j + weight[i] = W) { // dp[i][j]就是背包已經裝了j的重量時，能夠獲得的最大價值

                    dp[i][j] = Math.max(dp[i][j], value[i] + dp[i + 1][j + weight[i]]);

// 當背包重量為j時，要麼沿用剛剛裝的，本次不裝，最大價值dp[i][j]，要麼就把這個重物裝了，那麼此時背包裝的重量為j+weight[i]，

// 用本次的價值value[i]加上背包已經裝了j+weight[i]時還能獲得的最大價值，因為是從底下往上，剛剛上一步算過，可以直接用dp[i+1][j+weight[i]]。

// 然後選取本次不裝weight[i]重物時獲得的最大價值以及本次裝weight[i]重物獲得的最大價值兩者之間的最大值

                }

            }

        }

        return dp[0][0];

    }

}

_’>回溯法解決0-1背包問題 java寫的 求大神指點~~~~(>_

因為你把n和c 定義為static ,而且初始化為0,。數組也為靜態的,一個類中靜態的變量在這個類加載的時候就會執行，所以當你這類加載的時候，你的數組static int[] v = new int[n];

static int[] w = new int[n];

就已經初始化完畢，而且數組大小為0。在main方法里動態改變n的值是改變不了已經初始化完畢的數組的大小的，因為組已經加載完畢。

我建議你可以在定義n,c是就為其賦初值。比如（static int n=2 static int c=3）

java語言，背包問題，從Excel表中讀取數據

基本概念

問題雛形

01背包題目的雛形是：

有N件物品和一個容量為V的背包。第i件物品的體積是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。

從這個題目中可以看出，01背包的特點就是：每種物品僅有一件，可以選擇放或不放。

其狀態轉移方程是：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

對於這方方程其實並不難理解，方程之中，現在需要放置的是第i件物品，這件物品的體積是c[i],價值是w[i],因此f[i-1][v]代表的就是不將這件物品放入背包，而f[i-1][v-c[i]]+w[i]則是代表將第i件放入背包之後的總價值，比較兩者的價值，得出最大的價值存入現在的背包之中。

理解了這個方程後，將方程代入實際題目的應用之中，可得

for (i = 1; i = n; i++)

for (j = v; j = c[i]; j–)//在這裡，背包放入物品後，容量不斷的減少，直到再也放不進了

f[i][j] = max(f[i – 1][j], f[i – 1][j – c[i]] + w[i]);

問題描述

求出獲得最大價值的方案。

注意：在本題中，所有的體積值均為整數。

算法分析

對於背包問題，通常的處理方法是搜索。

用遞歸來完成搜索，算法設計如下：

int make(int i, int j)//處理到第i件物品,剩餘的空間為j 初始時i=m , j=背包總容量

{

if (i == 0) return 0;

if (j = c[i])//(背包剩餘空間可以放下物品 i )

{

int r1 = make(i – 1, j – w[i]);//第i件物品放入所能得到的價值

int r2 = make(i – 1, j);//第i件物品不放所能得到的價值

return min(r1, r2);

}

return make(i – 1, j);//放不下物品 i

}

這個算法的時間複雜度是O(n^2)，我們可以做一些簡單的優化。

由於本題中的所有物品的體積均為整數，經過幾次的選擇後背包的剩餘空間可能會相等，在搜索中會重複計算這些結點，所以，如果我們把搜索過程中計算過的結點的值記錄下來，以保證不重複計算的話，速度就會提高很多。這是簡單的“以空間換時間”。

我們發現，由於這些計算過程中會出現重疊的結點，符合動態規劃中子問題重疊的性質。

同時，可以看出如果通過第N次選擇得到的是一個最優解的話，那麼第N-1次選擇的結果一定也是一個最優解。這符合動態規劃中最優子問題的性質。

解決方案

考慮用動態規劃的方法來解決，這裡的：

階段：在前N件物品中，選取若干件物品放入背包中

狀態：在前N件物品中，選取若干件物品放入所剩空間為W的背包中的所能獲得的最大價值

決策：第N件物品放或者不放

由此可以寫出動態轉移方程：

我們用f[i][j]表示在前 i 件物品中選擇若干件放在已用空間為 j 的背包里所能獲得的最大價值

f[i][j] = max(f[i – 1][j – W[i]] + P[i], f[i – 1][j]);//j = W[ i ]

這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：“將前i件物品放入容量為v的背包中”這個子問題，若只考慮第i件物品的策略（放或不放），那麼就可以轉化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那麼問題就轉化為“前i-1件物品放入容量為v的背包中”，價值為f[v]；如果放第i件物品，那麼問題就轉化為“前i-1件物品放入已用的容量為c的背包中”，此時能獲得的最大價值就是f[c]再加上通過放入第i件物品獲得的價值w。

這樣，我們可以自底向上地得出在前M件物品中取出若干件放進背包能獲得的最大價值，也就是f[m,w]

算法設計如下：

int main()

{

cin n v;

for (int i = 1; i = n; i++)

cin c[i];//價值

for (int i = 1; i = n; i++)

cin w[i];//體積

for (int i = 1; i = n; i++)

f[i][0] = 0;

for (int i = 1; i = n; i++)

for (int j = 1; j = v; j++)

if (j = w[i])//背包容量夠大

f[i][j] = max(f[i – 1][j – w[i]] + c[i], f[i – 1][j]);

else//背包容量不足

f[i][j] = f[i – 1][j];

cout f[n][v] endl;

return 0;

}

由於是用了一個二重循環，這個算法的時間複雜度是O（n*w)。而用搜索的時候，當出現最壞的情況，也就是所有的結點都沒有重疊，那麼它的時間複雜度是O（2^n)。看上去前者要快很多。但是，可以發現在搜索中計算過的結點在動態規劃中也全都要計算，而且這裡算得更多（有一些在最後沒有派上用場的結點我們也必須計算），在這一點上好像是矛盾的。

01背包問題變種：從給定的N個正數中選取若干個數之和最接近M的JAVA寫法

BIAS0:= (C-MA(C,2))/MA(C,2)*100;

BIAS1 := (C-MA(C,12))/MA(C,12)*100;

BIAS2 := (C-MA(C,26))/MA(C,26)*100;

BIAS3 := (C-MA(C,48))/MA(C,48)*100;

HXL:=V/CAPITAL*100;

D1:=INDEXC;

D2:=MA(D1,56);

DR2:=D1/D20.94;

E1:=(C-HHV(C,12))/HHV(C,12)*10;

E2:=(C-REF(C,26))/REF(C,26)*10;

java寫背包問題沒看懂

m[][] 就是一個二維數組。

你平時看見的a[] 這樣的數組是用來定義一維數組的，裡面放的東西你應該明白。二維數組其實和一維數組差不多，只不過二維數組的m[]放的是另外一個m1[]這樣的數組。兩個數組就從線變成了面，類似於XY坐標圖了。這就是二維數組，面上的關係。