回溯法
N皇后
#include
#include
#define N 4
//皇后摆放结果 的 统计数组，索引：代表行； 元素值：代表列
int q[N + 1];
// 同列、同斜线 检查
int check(int j)
{
int i;
// 从第1个到 j-1个， 依次 和 第j个皇后 比对
for (i = 1; i < j; i++)
{
// q[i] == q[j] ： 同列判断
// abs(i-j) == abs(q[i] - q[j])： 同斜线判断
if (q[i] == q[j] || fabs(i - j) == fabs(q[i] - q[j]))
{
return 0;
}
}
return 1;
}
// 摆放 皇后
void queen()
{
int i;
// 皇后 数组 初始化
for (i = 1; i <= N; i++)
q[i] = 0;
int answer = 0; // 方案数，用来 统计 能找出来 几种方案
int j = 1; // 摆放 第j个皇后
while (j >= 1)
{
// 让当前 皇后 向后一列 摆放
q[j] += 1;
// q[i]<=N 不能超出范围
// ！check(j) 同列、同斜线 返回 0，取反为 true
while (q[j] <= N && !check(j))
{
// 摆放
// 综上： 在范围内 若 皇后 同行or同斜线 则 向后一列 摆放
q[j] += 1;
}
if (q[j] <= N) // 列数 判断
{
if (j == N) // 行数 判断
{ // 找到 N皇后 的 一组解，
answer = answer + 1;
printf("第%d种方案 的 答案为：", answer);
for (i = 1; i <= N; i++)
{
printf(" %d ", q[i]);
}
printf("回退回去 看看还能再找一组解吗 n");
}
else
{
j = j + 1; //放置 下一个 皇后；
}
}
else
{ // 当前行 的 皇后 没有合法的位置 需要 回溯 到 上一个皇后
q[j] = 0;
j = j - 1;
if(j==0) {
printf("找不到了，给 while 数一声，让他退出n");
}
}
}
}
int main()
{
queen();
return 0;
}
#include
#include
#define N 4
int answer = 0; //方案数
int q[N + 1]; //皇后 数组
// 同列、同斜线 检查, 对于if来说 0-->false 非0--->true
int check(int j)
{
int i;
for (i = 1; i < j; i++)
if (q[i] == q[j] || abs(i - j) == abs(q[i] - q[j]))
return 0;
return 1;
}
// 摆放 皇后
void queen(int j)
{
int i;
for (i = 1; i <= N; i++)
{
q[j] = i; // 放置一个位置
if (check(j)) // check(j) 不但检验合法性，也是 递归 的 结束条件
{
if (j == N)
{ // 找到一组解
answer++;
printf("第%d种方案 的 答案为：", answer);
for (i = 1; i <= N; i++)
{
printf(" %d ", q[i]);
}
printf("n");
// return;
}
else
{
queen(j + 1); // 递归摆放下一个 皇后 的位置
}
}
}
}
int main()
{
queen(1);
return 0;
}
分治法
最大子段和
#include
int MaxSubSum(int *Array, int left, int right)
{
int res;
// 一旦考虑用递归，就先写 递归限制条件!!!
if (left == right)
{
res = Array[left] > 0 ? Array[left] : 0;
}
else
{
// 划分左右的 中间轴 索引
int center = (left + right) / 2;
// 左子递归，向左拆分， 可获取 左子段 的 最大子段和
int leftsum = MaxSubSum(Array, left, center);
// 右子递归，向右拆分， 可获取 右子段 的 最大子段和
int rightsum = MaxSubSum(Array, center + 1, right);
// 计算 总的子段和 = 左子段和 + 右子段和
int i, tmp = 0, leftPart = 0; // leftPart 左子段和
for (i = center; i >= left; i--)
{
tmp += Array[i];
if (tmp > leftPart)
leftPart = tmp;
}
tmp = 0; // 临时变量 重新使用 就需要 初始化一次
int rightPart = 0; // rightPart 右子段和
for (i = center + 1; i <= right; i++)
{
tmp += Array[i];
if (tmp > rightPart)
rightPart = tmp;
}
// 总的子段和
res = leftPart + rightPart;
// 三者比较 谁大 谁为 最大子段和
if (leftsum > res)
res = leftsum;
if (rightsum > res)
res = rightsum;
}
return res;
}
int main()
{
int arr[6] = {-2, 11, -4, 13, -5, -2};
int res;
res = MaxSubSum(arr, 0, 5);
printf("%d", res);
return 0;
}
动态规划法
01背包
#include
#define N 4 // 物品数量
#define W 5 // 背包容量
int max(int a, int b)
{
return a > b ? a : b;
}
int main()
{
int v[] = {0, 2, 4, 5, 6}; // 物品价值数组
int w[] = {0, 1, 2, 3, 4}; // 物品重量数组
int f[N + 1][W + 1] = {}; // 子问题 的 真值表
int i, j; // i: 第i个物品， j：背包容量
for (i = 1; i <= N; i++)
{
for (j = 1; j <= W; j++)
{
if (j >= w[i])
{
//能否使用 case1 的条件判断，即 第i个物品 的重量 小等 背包容量
// case1 的 计算规则
f[i][j] = v[i] + f[i - 1][j - w[i]];
// 和 case2 的 计算规则 进行 比对 取最大值
f[i][j] = f[i][j] > f[i - 1][j] ? f[i][j] : f[i - 1][j];
}
else
{
// case2 的 计算规则
f[i][j] = f[i - 1][j];
}
}
}
// 将 最终 问题的解 打印出来
printf("%dn", f[N][W]);
return 0;
}
贪心法
部分背包
#include
#define N 5 // 物品数量
#define W 100 // 背包容量
// 部分背包 所能装载的 最大价值
// 调用前提： 已按照 单位总量价值 从大到小 排好序了
double MaxValue(int v[], int w[], double vw[])
{
double curVals = 0.0; // 当前背包承载总价值
int W_temp = W; // 背包容量
int i;
for (i = 1; i <= N; i++)
{
if (W_temp >= w[i])
{
W_temp = W_temp - w[i]; //装入当前 物品
curVals = curVals + v[i]; // 总价值 增加
}
else
{
// 容量 不够 装下一整个 物品的 时候 跳出循环
break;
}
}
// 如果 物品没装完，且 还有容量， 则 装入 部分物品
if (i <= N && W_temp > 0)
curVals = curVals + (double)W_temp / w[i] * v[i];
return curVals;
}
int main()
{
int v[] = {0, 65, 20, 30, 60, 40}; // 物品价值数组
int w[] = {0, 30, 10, 20, 50, 40}; // 物品重量数组
double vw[N + 1]; // 物品 单位重量 价值数组
int i;
for (i = 1; i <= N; i++)// 初始化 vw
vw[i] = (double)v[i] / w[i];
double res = MaxValue(v,w,vw);
printf("%f n", res); // 163.000
return 0;
}
