给定两个长度都为N的数组weights和values,weigths[i]和values[i]分别代表i号物品的重量和价值。
给定一个正数bag,表示一个载重bag的袋子,你装的物品不能超过这个重量。返回你能装下最多的价值是多少?
// 尝试 ,i...只管i后面能获取的最大值
public static int GetMaxValue(int [] weights,int [] values,int i,int bag,int curWeights){
if(curWeights > bag){
return 0;
}
if(i == weights.length){
return 0;
}
return Math.max(
// 不要i号货物,i+1位置决定
GetMaxValue(weights, values, i+1, bag, curWeights),
// 要i号货物,i+1决定后续,curWeights要加上这个重量
values[i] + GetMaxValue(weights, values, i+1, bag, curWeights + weights[i])
);
}