DP0/1背包问题
/***
* @author Administrator
* @version 2011.06.15
* 动态规划法解决0/1背包问题
*/
public class DPBeibao01 {
/**
* @param args
*/
public static void main(String[] args) {
int w[]={0,2,2,6,5,4};
int v[]={0,6,3,5,4,6};
System.out.println(maxValue(w,v,10));
}
/**
*
* @param w存放物品的重量
* @param v存放物品的价值
* @param c背包的容量
* @return
*/
private static int maxValue(int w[],int v[],int c){
int len=w.length;
//val表示把前i个物品放入容量为j的背包中得到的价值
int val[][]= new int;
for(int i=0;i<len;i++){
val=0;
}
for(int j=0;j<=c;j++){
val=0;
}
for(int i=1;i<len;i++){
for(int j=1;j<=c;j++){
if(w>j)val=val;
else{
val=Math.max(val, val]+v); }
}
}
int j=c;
int z[]=new int;//记录物品是否被装入背包中
for(int m=len-1;m>0;m--){
if(val==val)z=0;
else{
z=1;
j=j-v;
}
}
return val;
}
}
页:
[1]