01背包

public class Knapsack_01 {
public static int getBiggestValue(int[] w,int[] v,int bagWeight,int productNum){
int[][] V = new int[productNum + 1][bagWeight + 1];

    for(int i = 0;i < productNum + 1;++i){
        V[i][0] = 0;
    }
    for(int j = 0;j < bagWeight +1;++j){
        V[0][j] = 0;
    }
    
    for(int i = 1;i < productNum +1;++i){
        for(int j = 1; j < bagWeight+1;++j){
            if(j < w[i-1]){
                V[i][j] = V[i-1][j];
            }else if(j >= w[i-1]){
                if(V[i-1][j] > V[i-1][j-w[i-1]] + v[i-1]){
                    V[i][j] = V[i-1][j];
                }else{
                    V[i][j] = V[i-1][j-w[i-1]] + v[i-1];

// System.out.print(i + "---->");
}
}
}
}

    return V[productNum][bagWeight];
}

public static int getBiggestValue(int bagWeight,int[] v,int[] w,int[] vw){
    int maxValues = 0;
    int j = 0;
    
    for(int i =0;i < vw.length;++i){
        if(w[vw[i]] <= bagWeight-j){
            j += w[vw[i]];
            maxValues += v[vw[i]];
        }else{
            maxValues += ((bagWeight -j)* (v[i]/w[i]));
            j = bagWeight;
        }
    }
    return maxValues;
}
public static void main(String[] args){
int[] v = {20,30,65,40,60};

int[] w = {10,20,30,40,50};
int bagWeight = 100;

int productNum = 5;

System.out.println("01背包："+Knapsack_01.getBiggestValue(w,v,bagWeight,productNum));


int[] vf = {20,30,65,40,60};
int[] wf = {10,20,30,40,50};
int[] vwf = {2,0,1,4,3};
System.out.println("分数背包:"+Knapsack_01.getBiggestValue(bagWeight, vf, wf, vwf));
}

}