c++ - 类似于背包问题，能否教我如何用栈的方式解决

Question

某人的饭量为T，有n份体积分别为t1, t2, ... tn的美食，能否从n份美食中挑选若干份，使得恰好吃饱，也不浪费食物，求出所有满足条件的选择。

例： 请输入饭量T：T=10 请输入食品份数n：n=6 请输入6份食品的体积：1, 8, 4, 3, 5, 2 输出：可得到四组解：(1,4,3,2); (1,4,5); (8,2); (3,5,2)。

我的想法是设计一个自定义的整形栈来解决，但是没有成功。主要问题不知道如何将栈顶的数弹出， （1,4,5）和（3,5,2）两组解搞不出来。

Answer 1

首先抽象一下問題：

給定集合C和閾值m，要求找出C的所有符合條件的子集S，使得S的所有元素相加之和為m.

對於這個問題，其實一樣可以通過動態規劃進行求解。求解過程可以采用遞歸和非遞歸的形式，而一般所謂的遞歸形式(特例：[尾遞歸]，可以通過編譯器優化，轉換成非遞歸形式)，其實就是調用棧重複直接或間接調用自身的過程。所以通過棧的數據結構完全可以解決，而且這種解決方式，在一定程度上來說，就是把遞歸求解過程通過棧進行展開。閑話少說，上代碼(C 好久沒寫了，改用Java語言寫了一個實現，為了直觀體現求解過程，代碼中忽略了一些常規的數據校驗)：

package com.lee.test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PackageProblem {

public static void main(String[] args) {
    int[] problemSpace = {1, 8, 4, 3, 5, 2};
    int threshold = 10;

    printProblem(problemSpace, threshold);
    printSolution(solve(problemSpace, threshold));
}

private static void printProblem(int[] problemSpace, int threshold) {
    System.out.println("Problem Space : "+Arrays.toString(problemSpace));
    System.out.println("Problem threshold : "+threshold);
}

private static void printSolution(List<int[]> solutions) {
    System.out.println("Solutions : ");
    if(solutions == null || solutions.size() < 1) {
        System.out.println("no solution.");
    }else {
        for(int[] solution : solutions) {
            System.out.println(Arrays.toString(solution));
        }
    }
}

static class Element {
    int index;
    int value;

    Element(int index, int value) {
        this.index = index;
        this.value = value;
    }
}

static class Stack {
    private Element[] elements;
    private int top;
    private int sum;

    Stack(int capacity) {
        elements = new Element[capacity];
        top = -1;
        sum = 0;
    }

    void push(int index, int value) {
        if(top == elements.length - 1) {
            throw new IllegalStateException("stack is already full.");
        }
        elements[++top] = new Element(index, value);
        sum += value;
    }

    Element pop() {
        if(top == -1) {
            throw new IllegalStateException("stack is already empty.");
        }
        Element element = elements[top--];
        sum -= element.value;
        return element;
    }

    boolean isEmpty() { return top == -1; }

    int sum() { return sum; }

    int[] snapshot() {
        int[] snapshot = new int[top+1];
        for(int i=0; i<= top; i++) {
            snapshot[i] = elements[i].value;
        }

        return snapshot;
    }
}

private static List<int[]> solve(int[] problemSpace, int threshold) {
    if(problemSpace == null) {
        throw new NullPointerException("problem space is null.");
    }

    List<int[]> solutions = new ArrayList<int[]>();
    if(problemSpace.length < 1) {
        return solutions;
    }

    Stack stack = new Stack(problemSpace.length);
    stack.push(0, problemSpace[0]);
    int index = 0;
    while(true) {
        int sum = stack.sum();
        if(sum >= threshold) {
            if(sum == threshold) {
                solutions.add(stack.snapshot());
            }
            index = stack.pop().index;
        }

        if(index < problemSpace.length - 1) {
            stack.push(++index, problemSpace[index]);
        }else {
            if(sum < threshold) { stack.pop(); }
            if(stack.isEmpty()) { break; }
            index = stack.pop().index;
        }
    }

    return solutions;
}

}

PS: 自己運行了一下，應該是Ok，有什麼問題，歡迎留言