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));
}
}
