算法回忆录（3）

11. 假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，设计算法求解怎么装才能使得获取的价值最大？请写出伪代码。

#include <stdio.h>#define MAX_ITEMS 100
#define MAX_WEIGHT 1000int max(int a, int b) {return (a > b) ? a : b;
}// 动态规划求解背包问题
void knapsack(int n, int capacity, int weights[], int values[]) {int dp[MAX_ITEMS + 1][MAX_WEIGHT + 1] = {0};int i, w;// 填表格for (i = 1; i <= n; i++) {for (w = 1; w <= capacity; w++) {if (weights[i - 1] > w) {dp[i][w] = dp[i - 1][w];} else {dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);}}}// 回溯找出装入背包的物品int res[MAX_ITEMS];int k = n, c = capacity;int num = 0;while (k > 0 && c > 0) {if (dp[k][c] != dp[k - 1][c]) {res[num++] = k;c -= weights[k - 1];}k--;}// 输出结果for (i = num - 1; i >= 0; i--) {printf("%-d ", res[i]);}printf("\n");printf("end");
}int main() {int n, capacity;scanf("%d %d", &n, &capacity);int weights[MAX_ITEMS], values[MAX_ITEMS];for (int i = 0; i < n; i++) {scanf("%d", &weights[i]);}for (int i = 0; i < n; i++) {scanf("%d", &values[i]);}// 调用背包问题求解函数knapsack(n, capacity, weights, values);return 0;
}

运行结果：

12. 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 或 3 个台阶。你有多少种不同的方法可以爬到楼顶呢？请用动态规划算法解决并写出伪代码。（n需要在算法中输入）

#include <stdio.h>int climbStairs(int n) 
{int dp[n];dp[0] = 1;dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++){dp[i] = dp[i-1] + dp[i-2]+dp[i-3];}return dp[n];
}int main(){int n ;scanf("%d",&n);int result = climbStairs(n);printf("%d\n", result); // 输出结果return 0;
}

运行结果：

13.最长公共子序列是指两个序列共同拥有的最长的子序列，这个子序列在两个序列中的位置不必连续，但必须保持原有的顺序。例如，对于序列X=“ABCBDAB”和序列Y=“BDCABA”，它们的最长公共子序列为“BCBA”，长度为4。编程输入两个字符串，求其最长公共子序列的长度。

#include <stdio.h>  
#include <string.h>  // 函数声明  
int longestCommonSubsequence(char *X, char *Y);  int main() {  char X[100], Y[100];  // 输入两个字符串  printf("Enter the first string: ");  scanf("%99s", X); // 使用%99s限制输入长度，避免溢出  printf("Enter the second string: ");  scanf("%99s", Y);  // 调用函数计算LCS长度  int length = longestCommonSubsequence(X, Y);  // 输出LCS长度  printf("The length of the Longest Common Subsequence is: %d\n", length);  return 0;  
}  // 函数定义：计算两个字符串的最长公共子序列的长度  
int longestCommonSubsequence(char *X, char *Y) {  int m = strlen(X);  int n = strlen(Y);  // 创建一个二维数组dp，用于存储子问题的解  int dp[m + 1][n + 1];  // 初始化dp数组  for (int i = 0; i <= m; i++) {  for (int j = 0; j <= n; j++) {  if (i == 0 || j == 0) {  dp[i][j] = 0;  }  }  }  // 填充dp数组  for (int i = 1; i <= m; i++) {  for (int j = 1; j <= n; j++) {  if (X[i - 1] == Y[j - 1]) {  dp[i][j] = dp[i - 1][j - 1] + 1;  } else {  dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];  }  }  }  // dp[m][n]存储了X和Y的最长公共子序列的长度  return dp[m][n];  
}

运行结果：

14. 填入0~9的数字。要求：连续的两个数字不能相邻。（左右.上下.对角都算相邻）一共有多少种可能的填数方案？请输出一个表示方案数目的整数。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>int disp(int a[], int n) {int i;for (i = 0; i < 9; i++) {if (abs(a[i] - a[i + 1]) == 1 && i != 2 && i != 6)return 0;}for (i = 0; i < 6; i++) {if (abs(a[i] - a[i + 4]) == 1)return 0;}for (i = 0; i < 7; i++) {if (abs(a[i] - a[i + 3]) == 1 && i != 3)return 0;}for (i = 0; i < 5; i++) {if (abs(a[i] - a[i + 5]) == 1 && i != 2)return 0;}return 1;
}void swap(int *xp, int *yp) {int temp = *xp;*xp = *yp;*yp = temp;
}void permute(int *a, int l, int r, int *count) {int i;if (l == r) {if (disp(a, r + 1)) {(*count)++;}} else {for (i = l; i <= r; i++) {swap((a + l), (a + i));permute(a, l + 1, r, count);swap((a + l), (a + i)); // backtrack}}
}int main() {int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};int n = 10;int count = 0;permute(a, 0, n - 1, &count);printf("%d\n", count);return 0;
}

运行结果：

15. 编程输出一个特别的数，该数是一个由1~9组成的9位数，每个数字只能出现一次，且这个9位数由高位到低位前i位能被i整除。

#include <stdio.h>
int main(void)
{
long i[9];
long j, n;
i[4] = 5;
for (i[0] = 1; i[0] < 10; i[0] += 2)
{
for (i[1] = 2; i[1] < 9; i[1] += 2)
{
for (i[2] = 1; i[2] < 10; i[2] += 2)
{
if (i[2] == i[0])
continue;
for (i[3] = 2; i[3] < 9; i[3] += 2)
{
if (i[3] == i[1])
continue;
for (i[5] = 2; i[5] < 9; i[5] += 2)
{
if (i[5] == i[3] || i[5] == i[1])
continue;
for (i[6] = 1; i[6] < 10; i[6] += 2)
{
if (i[6] == i[4] || i[6] == i[2] || i[6] == i[0])
continue;
for (i[7] = 2; i[7] < 9; i[7] += 2)
{
if (i[7] == i[5] || i[7] == i[3] || i[7] == i[1])
continue;
for (i[8] = 1; i[8] < 10; i[8] += 2)
{
if (i[8] == i[6] || i[8] == i[4] || i[8] == i[2] || i[8] == i[0])
continue;
n = 0;
for (j = 0; j < 9; j++)
{
n = n * 10 + i[j];
if (n % (j + 1) != 0)
break;
}
if (j == 9)
printf("%ld\n", n);
}
}
}
}
}
}
}
}
}