算法问题---两艘船是否有最大承载量

算法问题—两艘船是否有最大承载量

代码：

栈代码：

#pragma once #include<stdio.h> #define maxSize 100 typedef struct stack {int * base;int * top; }stack; bool init(stack & Stack) {//栈的初始化Stack.base = new int[maxSize];if (!Stack.base) {return false;}Stack.top = Stack.base;return true; } bool push(stack & Stack,int e) {//入栈if (Stack.top - Stack.base == maxSize) {//满栈，不能再插入return false;}*(Stack.top) = e;Stack.top++;return true; } bool pop(stack & Stack, int &e) {//出栈if (Stack.base == Stack.top) {//栈空return false;}Stack.top--;e = *(Stack.top);return true; } int getTop(stack &Stack) {if (Stack.base == Stack.top) {//栈空return -1;}return *(Stack.top - 1); } void printStack(stack Stack) {//遍历栈中的元素while (Stack.base != Stack.top) {printf("%d ", *(Stack.top - 1));Stack.top--;} } bool empty(stack Stack) {//栈空的判断if (Stack.base == Stack.top) {return true;}return false; } void testStack() {//测试栈是否有问题stack Stack;init(Stack);int value;while (1) {scanf_s("%d", &value);if (value == -1) {break;}push(Stack, value);}printStack(Stack); }

算法关键代码：

#include<stdio.h> #include<stdlib.h> #include"stack.h" #define N 100 int c1=0, c2=0;//两艘船的最大承载量 int weights[N]; int bestWeight=0, curWeight=0;//分配给一个船的全部方式分配的最佳重量和当前这样分配的最佳重量 void backTrace(int i23,int n, stack Stack23) {//递归if (i23 == n) {//结束的条件if (curWeight > bestWeight) {bestWeight = curWeight;//每种分配方式的最佳重量int * v = Stack23.top;printStack(Stack23);Stack23.top = v;printf("\n");}return;//递归一定要有结束}if (curWeight + weights[i23] <= c1) {curWeight += weights[i23];push(Stack23, i23);backTrace(i23 + 1,n, Stack23);curWeight -= weights[i23];int e;pop(Stack23, e);}backTrace(i23 + 1, n, Stack23); } int main() {int n,sum=0;stack Stack23;init(Stack23);scanf_s("%d%d%d",&c1, &c2, &n);//c1和c2不能一下子全局变量一下又局部变量，这样会出现被局部变量占用，并随便乱赋值的错误结果for (int i = 0; i < n; i++) {int tempV;scanf_s("%d", &tempV);weights[i] = tempV;sum += tempV;}backTrace(0, n, Stack23);if (sum - bestWeight <= c2) {printf("能够分配好！\n");}else {printf("不能够分配好！\n");}system("pause");return 0; }

测试截图：

时间复杂度O(n),空间复杂度O(n)

如果存在什么问题，欢迎批评指正！谢谢！

总结

以上是生活随笔为你收集整理的算法问题---两艘船是否有最大承载量的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。