chihungyu1116
BAN USERRecursion, test it simply copy and paste this in your console!
function knapack(require_amount){
var a = {
quantity: 10,
price: 100
}
var b = {
quantity: 20,
price: 200
}
var c = {
quantity: 30,
price: 120
}
var d = {
quantity:15,
price: 130
}
var e = {
quantity: 25,
price: 165
}
var arr = [a,b,c,d,e];
return min_price(arr, require_amount, 0);
}
function min_price(arr, require_amount, price){
if(require_amount === 0) return price;
if(require_amount < 0) return Infinity;
var result_arr = [];
for(var i = 0; i < arr.length; i++){
var item = min_price(arr, require_amount - arr[i].quantity, price + arr[i].price);
result_arr.push(item);
}
return Math.min.apply(null, result_arr);
}
knapack(100);
var arr = [5, 6, 1, 2, 3, 4] ;
- chihungyu1116 January 19, 2014First get then length of the array.
var len = arr.length;
Then concat the array with itself
arr = arr.concat(arr);
now you get [1, 2, 3, 4, 5, 6, 1, 2, 3, 4]
truncate the array
arr = arr.slice(0, len);
then you do a binary search.