c語言貪心演算法程序

㈠ c語言貪心演算法智力大沖浪與花生採摘兩題

都是用C++寫的，不建議只用純C語言

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

struct Riddle {
int time;
int money;
};

struct gt{
bool operator()(Riddle& opl, Riddle& opr){
return opl.money > opr.money;
}
};

int main()
{
int m, n;
ifstream fin("riddle.in");
fin >> m >> n;
Riddle * riddles = new Riddle[n];
for (int i=0; i<n; ++i) {
fin >> riddles[i].time;
}
for (int i=0; i<n; ++i) {
fin >> riddles[i].money;
}
sort(riddles, riddles+n, gt() );

int * ridorder = new int[n];
for (int i=0; i<n; ++i) {
ridorder[i] = 0;
}
for (int i=0; i<n; ++i) {
int j;
for (j=riddles[i].time-1; j>=0 && ridorder[j]!=0; --j) {}

if (j >= 0) ridorder[j] = 1;
else m -= riddles[i].money;
}
cout << m << endl;
}

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

#define maxn 55

struct Peanut
{
int x, y, num;
}peanut[maxn * maxn];

int n, m, t, pcount;

bool operator < (const Peanut &a, const Peanut &b)
{
return a.num > b.num;
}

void input()
{
pcount = 0;
scanf("%d%d%d", &n, &m, &t);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
int a;
scanf("%d", &a);
if (a)
{
peanut[pcount].x = i + 1;
peanut[pcount].y = j + 1;
peanut[pcount].num = a;
pcount++;
}
}
}

void work()
{
int nowtime = peanut[0].x + 1;
if (nowtime + peanut[0].x > t)
{
printf("0\n");
return;
}
int ans = peanut[0].num;
for (int i = 1; i < pcount; i++)
{
nowtime += abs(peanut[i].x - peanut[i - 1].x) + abs(peanut[i].y - peanut[i - 1].y) + 1;
if (nowtime + peanut[i].x > t)
break;
ans += peanut[i].num;
}
printf("%d\n", ans);
}

int main()
{
//freopen("t.txt", "r", stdin);
int t;
scanf("%d", &t);
while (t--)
{
input();
sort(peanut, peanut + pcount);
work();
}
return 0;
}

㈡ C語言 貪心演算法求背包問題

是你的冒泡排序出了問題~

你吧 原來的1-2-3號按照東西的價值重新排列現在的1-2-3對應原來的2-1-3了
所以 你輸出的時候是按 1-2-3輸出的話 就等於第一個是原來的X2 第二個是X1第三個是X3
而且你的冒泡排序用錯了 只比較了 P[0]/K[0]和P[1]/K[1] P[1]/K[1]和P[2]/K[2]
周一我去學校幫你重新改改 我家的機器沒有C++
周一晚上我會上傳答案~我最近正好也要做演算法的作業~
#include <stdio.h>
#include <math.h>
#define N 50

float find(float p[N],float w[N],float x[N] ,float M,int n) /*先放單位價值量大的物體，再考慮小的物體*/
{
int i;
float maxprice;
for (i = 0; i < n; i++)
x[i] = 0;
i = 0;
maxprice=0;
while (i < n && w[i] < M)
{
M=M-w[i];
x[i] =w[i]; /* 表示放入數量 */
maxprice=maxprice+p[i];
x[n-1]=M;
i++;
}
if (i < n &&M> 0)
{
maxprice=maxprice+p[i]*x[i]/w[i];
i++;
}
return maxprice;
}

int main()
{
int n,flag=1;
float temp,M,w[N],p[N],x[N];
int a[N],b[N];
int k,j,l=0;
printf(

㈢ C語言中prime的作用

prime的作用就是判斷一個數是否為素數（也稱「質數」）。

例如：

#include<stdio.h>

intIsPrime(intn)

{

if(n<=1)return0;

if(n%2==0)returnn==2;

for(inti=3;;i+=2)

{

if(i>n/i)break;//等價於i*i>n,不用開方

if(n%i==0)return0;

}

return1;

}

intmain()

{

for(intn=100;n<=300;n++)

if(IsPrime(n))

printf("%4d",n);

return0;

}

(3)c語言貪心演算法程序擴展閱讀：

prime演算法

prime是以點為基礎出發進行檢索最小生成樹的一種貪心演算法。

思想：

將所有的點分成兩類，一類是已經放到碗里的，另一類是還沒有有放到碗里的，可以通過一個數組bool visit[]來記錄這個點到底是屬於第一類還是屬於第二類之後每一個周期索要進行的操作，找出一一定范圍內路徑的的范圍的最小值。

所有的從第一類點直接連接到第二類點的邊將最小的邊記錄下來（這個也就是生成樹中的一條邊）將這個新邊（這個一個連接第一類點和第二類點的邊）連到的那個第二類點歸類到第一類點中，之後重復這個操作，最終消滅所有的第二類點。

假設有n個節點，我最初給出一個點，以這個點開始進行搜索，這個時候該點為第一類點，其餘n-1個點為第二類點。之後進行n-1次操作，一共選出了n-1個邊（符合樹的性質），構成了最小生成樹。