84669 人學習
152542 人學習
20005 人學習
5487 人學習
7821 人學習
359900 人學習
3350 人學習
180660 人學習
48569 人學習
18603 人學習
40936 人學習
1549 人學習
1183 人學習
32909 人學習
某人的饭量为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)两组解搞不出来。
欢迎选择我的课程,让我们一起见证您的进步~~
首先抽象一下问题:
给定集合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,有什么问题,欢迎留言
首先抽象一下问题:
对于这个问题,其实一样可以通过动态规划进行求解。求解过程可以采用递归和非递归的形式,而一般所谓的递归形式(特例:[尾递归],可以通过编译器优化,转换成非递归形式),其实就是调用栈重复直接或间接调用自身的过程。所以通过栈的数据结构完全可以解决,而且这种解决方式,在一定程度上来说,就是把递归求解过程通过栈进行展开。闲话少说,上代码(C++好久没写了,改用Java语言写了一个实现,为了直观体现求解过程,代码中忽略了一些常规的数据校验):
PS: 自己运行了一下,应该是Ok,有什么问题,欢迎留言