01背包问题--Java

关于01背包，网上很少用Java完成，大多是用c/c++,这让学习Java的非常难受，比如我，今天终于把01背包搞清楚了，趁热打铁，为此写下此博。。。。

例如：一个背包可以装重量为10的物品，现在有重量分别为2、3 、4 、5、8、9的物品，其价值分别为3、4、5、8、10.问这样才能使背包的到最大价值？

首先送上公式：

B[k][c]=Math.max（value1，value2）；当第k个物品的重量大于当前所剩重量时：B[k-1][c]，当小于时分两种情况：选择不装入k,那么value1=B[k-1][c]，装入k:  value2=B[k-1][c-w[k]+v[k](w[k]为第k个的重量，v[k]为第k个的价值).

送上一个背包模拟网站http://www.karaffeltut.com/NEWKaraffeltutCom/Knapsack/knapsack.html

Java：

import java.util.Scanner;


public class 我的背包 {
static int N=6,W=11;
static int [][]B=new int [N][W];
public static void cap(int w[],int V[]){

for(int k=1;k<N;k++){
for(int c=1;c<W;c++){
if(w[k]>c){//不能装入
B[k][c]=B[k-1][c];
}else {
int value1=B[k-1][c-w[k]]+V[k];//选择装入
int value2=B[k-1][c];//选择不装
B[k][c]=Math.max(value1, value2);看装与不装那个的价值大
}
}
}
}
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int w[]=new int[N];
int v[]=new int[W];
w[0]=0;
v[0]=0;
for(int i=1;i<N;i++){
w[i]=in.nextInt();
v[i]=in.nextInt();
}
cap(w,v);
System.out.println(B[5][10]);
}
}