貪心算法—寶藏最優選擇問題

原理參考趣學算法

代碼：

#include"quickSort1.h"
快速排序代碼

int quickSort1(int a[], int l, int h) {//快速排序int i = l, j = h, p = a[l];while (i < j) {while (i<j&&a[j]>p) {//從右往左遍歷查找比p更小的元素j--;}if (i < j) {a[i++] = a[j];}while (i < j&&a[i] <= p) {//從左往右遍歷查找比p更大的元素i++;}if (i < j) {a[j--] = a[i];}}a[i] = p;//分界的值，左邊小于等于p，右邊大于preturn i; } void fenZhi1(int a[], int l, int h) {//分治if (l < h) {int mid = quickSort1(a, l, h);//以mid為分界線，進行分治，然后遞歸下去排序fenZhi1(a, l, mid - 1);fenZhi1(a, mid + 1, h);} }

貪心代碼

#include <stdio.h> #include <stdlib.h> #include"quickSort1.h" void getBestValue(int * a,int bestWeight,int n) {//等值物品的最優選擇問題int tempSum = 0;//臨時總和量int pointCount = 0;//前個數for (int i = 0; i < n; i++) {tempSum += *(a + i);if (tempSum > bestWeight) {pointCount = i;break;}printf("%d ", *(a + i));}printf("\n總共%d個！\n",pointCount); } int main() {int b[7] = { 1,6,4,3,9,7,5 };int length = sizeof(b) / sizeof(b[0]);fenZhi1(b, 0, length - 1);getBestValue(b, 17, length);system("pause");return 0; }

測試：

時間復雜度O(nlogn)，空間復雜度O(1)

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

總結

以上是生活随笔為你收集整理的算法---宝藏最优选择问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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