求哪几个数字之和接近某一个给定的值（小于等于）

Question

生活中，经常会有这样一个情况：

网上购物，一张固定的购物券1000，有很多商品，单价不同，101，230，330，210，299，...
怎样才能尽可能的使用完这1000元。

这只是一个例子，具体转换成计算机专业的描述我不知道该怎么表达，
如题：求哪几个数字之和接近某一个给定的值（小于等于）

这样一个业务逻辑，该用怎样的算法呢？不限语言。（c,php,java,node）

Answer 1

这种问题属于背包问题范畴，可采用贪心算法进行解决。

Answer 2

01背包问题

Answer 3

这是典型的01背包问题，最常见的是用动态规划解决

Answer 4

这道题, 其实他和另外一道题很相似,
有一个数组arr = [1,2,3,4,5,6,7],数组内的哪些元素相加, 和等于 8?
编写函数build(arr, n) 返回 [ [ 1, 2, 5 ], [ 1, 3, 4 ], [ 1, 7 ], [ 2, 6 ], [ 3, 5 ] ]

不同之处在于, 你这个是 求小于等于, 且仅要求最接近, 只需要将代码稍加改造,
先上 上面那个问题的代码,

function buildArr(arr, lim) {
    arr = [... new Set(arr.filter(item => item <= lim && item > 0).sort((a, b) => a > b))];
    var result = [];
    var len = arr.length;
    each(-1, [], 0);
    function each(s, a, n) {
        for(var i = s +1; i < len && n < lim; i++) {
            var A = [... a, arr[i]];
            var N = n + arr[i];
            if(N < lim) {
                each(i, A, N);
            } else if(N == lim) {
                result.push(A);
            }
        }

    }
    return result;
}
console.log(buildArr([1,2,3,4,5,6,7], 8));

再来看你这个问题, 其实稍加改造,

function buildArr(arr, lim) {
    arr = [... new Set(arr.filter(item => item <= lim && item > 0).sort((a, b) => a > b))];
    var result = [];
    var num = 0;
    var len = arr.length;
    each(-1, [], 0);
    function each(s, a, n) {
        if(n == lim) {
            return;
        }
        for(var i = s +1; i < len && n < lim; i++) {
            var A = [... a, arr[i]];
            var N = n + arr[i];
            if(N < lim) {
                if(N > num) {
                    result = A;
                    num = N;
                }
                each(i, A, N);
            } else if(N == lim) {
                result = A;
                num = N;
            }
        }

    }
    return result;
}

这样就可以了...