正常情况下求具体最优方案，需要用一个二维的表来记录选(1)还是不选(0)当前物品i。输出方案的时候需要从表的右下角N,C开始，从右(下)到左(上)来输出物品选择：如果当前物品i记录的是选(1)，那么i物品加入背包，看 i-1,c-ci; 如果是不选(0)，那么直接看 i-1,c. 这样物品输出是倒序的，我们无法通过倒序来判断字典序。

所以一个想法是在DP状态里面，我们重新给物品标号，我们让第1个物品是指的容量是c(N)价值是v(N)的那个物品，以此类推，第i个物品是指input的第N-i+1个物品。那么这样在从后往前找方案的时候，物品选择是正序的。

正序选择的话，如何判断字典序最小呢，那就是对于dp状态i （物品N-i+1），如果选和不选价值都一样，我们需要走选的那个路径。如果不选的话，之后肯定会选一个比N-i+1还大的物品，导致字典序变大。（其实这是一个贪婪算法，对于选i的方案A和不选i的方案B，对于i之后下一个物品选择，方案B的序号是>=方案A的序号的。所以无论如何，方案A都是字典序最小的方案，严谨证明就不写了）

private static List<Integer> knapsackDPSolution(int N, int C, int[] ss, int[] vs) {
    int[] dp = new int[C+1];
    int[][] g = new int[N+1][C+1]; // 0 means not pick, 1 means pick

    for (int i=1; i<=N; i++) {
        int k = N-i; // consider the array is N....1, first item is actually last one
        for (int j=C; j>=ss[k]; j--) {
            int pickValue = dp[j-ss[k]] + vs[k];
            int notPickValue = dp[j];
            g[i][j] = notPickValue > pickValue ? 0 : 1;
            dp[j] = Math.max(notPickValue, pickValue);
        }
    }

    List<Integer> ans = new ArrayList<>();

    // Try to trace back to get selections
    int c = C;
    for (int i=N; i>=1; i--) {
        if (g[i][c] == 1) {
            ans.add(N-i+1);
            c -= ss[N-i];
        }
    }

    return ans;
}