算法問題—兩艘船是否有最大承載量

代碼：

棧代碼：

#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); }

算法關(guān)鍵代碼：

#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) {//結(jié)束的條件if (curWeight > bestWeight) {bestWeight = curWeight;//每種分配方式的最佳重量int * v = Stack23.top;printStack(Stack23);Stack23.top = v;printf("\n");}return;//遞歸一定要有結(jié)束}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不能一下子全局變量一下又局部變量，這樣會出現(xiàn)被局部變量占用，并隨便亂賦值的錯誤結(jié)果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)

如果存在什么問題，歡迎批評指正！謝謝！

總結(jié)

以上是生活随笔為你收集整理的算法问题---两艘船是否有最大承载量的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。