算法----最大承載量下的最大價值問題

代碼：

棧代碼：（存儲哪些是需要的價值物）

#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" int MaxValues = 0, tempValues = 0;//最大價值和每次遞歸從樹根到葉子結點的最大價值 int tempWeight = 0, maxWeight;//本次從根節點到其中一個葉子結點的最大臨時重量和人能承載的最大重量 int w[100],p[100];//每個寶貝物品的重量和價值 stack Stack24; void backTrace(int h,int maxH) {//最大承載量下的最大價值if (h == maxH) {if (tempValues > MaxValues) {MaxValues = tempValues;int * v = Stack24.top;printStack(Stack24);Stack24.top = v;printf("\n");}return;}if (tempWeight + w[h] <= maxWeight) {tempWeight += w[h];tempValues += p[h];push(Stack24, h);backTrace(h + 1, maxH);tempWeight -= w[h];tempValues -= p[h];int e;pop(Stack24, e);}backTrace(h + 1, maxH); } int main() {init(Stack24);int n;scanf_s("%d%d", &maxWeight,&n);for (int i = 0; i < n; i++) {scanf_s("%d%d", &w[i],&p[i]);}backTrace(0, n);printf("最大承載量下的最大價值為:%d\n",MaxValues);system("pause");return 0; }

測試截圖：

時間復雜度O(n),空間復雜度O(1)

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

總結

以上是生活随笔為你收集整理的算法----最大承载量下的最大价值问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。