用限额最大化总和

Question

我必须得到一些不超过限制的数字的最高总和。

对于具有5,7，14和13一个实施例的限制，我必须选择5和7

这个例子是仅具有3个数字，但是我有能够与很多更多的数字要做到这一点。

有没有图书馆或方法来做到这一点？

Answer 1

我假设允许的输入是正整数。这将在您的问题中返回[7, 5]作为示例。

public class Knapsack { 
    private class State { 
    State previousState = null; 
    int value = 0; 
    } 

    public List<Integer> solve(List<Integer> list, int limit) { 
    // validate input 
    if (limit < 0) { 
     throw new IllegalArgumentException(); 
    } 
    if (list == null) { 
     throw new IllegalArgumentException(); 
    } 
    for (Integer i: list) { 
     if (i == null || i.intValue() <= 0) { 
     throw new IllegalArgumentException(); 
     } 
    } 

    // if the limit is 12, then 0 through 12 inclusive are valid amounts 
    State[] states = new State[limit + 1]; 
    // the state at position x represents a way of achieving a sum of x 
    // if a state is null it means we can't get that sum, for example in your 
    // question there's no way to get a sum of 11 with any combination of inputs 

    // base state -- we can always get a sum of zero if we just take nothing 
    states[0] = new State(); 

    // build up more states 
    for (Integer i: list) { 
     // iterate through the states backwards 
     // if we iterate forwards we'll encounter any changes we make to the list 
     // during the iteration, which has the effect of taking the same number 
     // multiple times 
     for (int j = limit - i.intValue(); j >= 0; --j) { 
     if (states[j] != null) { 
      State newState = new State(); 
      newState.previousState = states[j]; 
      newState.value = i.intValue(); 
      states[i.intValue() + j] = newState; 
     } 
     } 
    } 

    // find the best state 
    State s = null; 
    for (int i = limit; i >= 0; --i) { 
     if (states[i] != null) { 
     // if all you care about is the best achievable sum, you can just 
     // return i here 
     s = states[i]; 
     break; 
     } 
    } 

    // build the list of numbers 
    List<Integer> ret = new ArrayList<Integer>(); 
    while (s.previousState != null) { 
     // this will add them backwards, change to add to the beginning of the list 
     // to preserve the same order as the input 
     ret.add(Integer.valueOf(s.value)); 
     s = s.previousState; 
    } 

    return ret; 
    } 

    public static void main(String[] arg) { 
    List<Integer> list = new ArrayList<Integer>(); 
    for (int i: new int[] { 5, 7, 9 }) { 
     list.add(Integer.valueOf(i)); 
    } 
    int limit = 13; 

    Knapsack k = new Knapsack(); 
    System.out.println(k.solve(list, limit)); 
    } 
}