某人的饭量为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)两组解搞不出来。
PHP中文网2017-04-17 11:12:31
首先抽象一下问题:
给定集合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,有什么问题,欢迎留言