算法1的c代码和伪代码
时间: 2023-11-18 11:20:52 浏览: 22
C代码:
void insertion_sort(int arr[], int n) {
int i, j, temp;
for(i = 1; i < n; i++) {
temp = arr[i];
for(j = i - 1; j >= 0 && arr[j] > temp; j--)
arr[j+1] = arr[j];
arr[j+1] = temp;
}
}
伪代码:
INSERTION_SORT(A)
for i = 1 to length[A] - 1
key = A[i]
j = i - 1
while j >= 0 and A[j] > key
A[j+1] = A[j]
j = j - 1
A[j+1] = key
相关问题
算法背包问题代码和伪代码c语言
一、01背包问题
伪代码:
1.初始化dp数组,dp[i][0] = 0,dp[0][j] = 0
2.对于每个物品i,从j = 1到j = V,逆序枚举背包容量:
3.如果j < w[i],说明这个物品放不下,则dp[i][j] = dp[i-1][j]
4.否则,dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])
5.最终结果存储在dp[N][V]中
C++代码:
int dp[MAX_N][MAX_V]; // dp数组
int w[MAX_N], v[MAX_N]; // 物品的重量和价值
int N, V; // 物品数量和背包容量
int solve() {
memset(dp, 0, sizeof(dp)); // 初始化dp数组
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= V; j++) {
if (j < w[i]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
}
}
}
return dp[N][V]; // 返回最终结果
}
二、完全背包问题
伪代码:
1.初始化dp数组,dp[i][0] = 0,dp[0][j] = 0
2.对于每个物品i,从j = 1到j = V,正序枚举背包容量:
3.对于每个物品i,从j = w[i]到j = V,正序枚举背包容量:
4.dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]]+v[i])
5.最终结果存储在dp[N][V]中
C++代码:
int dp[MAX_N][MAX_V]; // dp数组
int w[MAX_N], v[MAX_N]; // 物品的重量和价值
int N, V; // 物品数量和背包容量
int solve() {
memset(dp, 0, sizeof(dp)); // 初始化dp数组
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= V; j++) {
for (int k = 0; k*w[i] <= j; k++) {
dp[i][j] = max(dp[i][j], dp[i-1][j-k*w[i]]+k*v[i]);
}
}
}
return dp[N][V]; // 返回最终结果
}
三、多重背包问题
伪代码:
1.初始化dp数组,dp[i][0] = 0,dp[0][j] = 0
2.对于每个物品i,从j = 1到j = V,正序枚举背包容量:
3.对于每个物品i,从j = w[i]到j = V,正序枚举背包容量:
4.对于每个物品i,从k = 0到k = min(v[i], j/w[i]),正序枚举物品数量:
5.dp[i][j] = max(dp[i][j], dp[i-1][j-k*w[i]]+k*v[i])
6.最终结果存储在dp[N][V]中
C++代码:
int dp[MAX_N][MAX_V]; // dp数组
int w[MAX_N], v[MAX_N]; // 物品的重量和价值
int N, V; // 物品数量和背包容量
int solve() {
memset(dp, 0, sizeof(dp)); // 初始化dp数组
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= V; j++) {
for (int k = 0; k <= min(v[i], j/w[i]); k++) {
dp[i][j] = max(dp[i][j], dp[i-1][j-k*w[i]]+k*v[i]);
}
}
}
return dp[N][V]; // 返回最终结果
}
算法背包问题代码和伪代码C语言
一、01背包问题
伪代码:
1.初始化dp数组,dp[i][0] = 0,dp[0][j] = 0
2.对于每个物品i,从j = 1到j = V,逆序枚举背包容量:
3.如果j < w[i],说明这个物品放不下,则dp[i][j] = dp[i-1][j]
4.否则,dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])
5.最终结果存储在dp[N][V]中
C++代码:
int dp[MAX_N][MAX_V]; // dp数组
int w[MAX_N], v[MAX_N]; // 物品的重量和价值
int N, V; // 物品数量和背包容量
int solve() {
memset(dp, 0, sizeof(dp)); // 初始化dp数组
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= V; j++) {
if (j < w[i]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
}
}
}
return dp[N][V]; // 返回最终结果
}
二、完全背包问题
伪代码:
1.初始化dp数组,dp[i][0] = 0,dp[0][j] = 0
2.对于每个物品i,从j = 1到j = V,正序枚举背包容量:
3.对于每个物品i,从j = w[i]到j = V,正序枚举背包容量:
4.dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]]+v[i])
5.最终结果存储在dp[N][V]中
C++代码:
int dp[MAX_N][MAX_V]; // dp数组
int w[MAX_N], v[MAX_N]; // 物品的重量和价值
int N, V; // 物品数量和背包容量
int solve() {
memset(dp, 0, sizeof(dp)); // 初始化dp数组
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= V; j++) {
for (int k = 0; k*w[i] <= j; k++) {
dp[i][j] = max(dp[i][j], dp[i-1][j-k*w[i]]+k*v[i]);
}
}
}
return dp[N][V]; // 返回最终结果
}
三、多重背包问题
伪代码:
1.初始化dp数组,dp[i][0] = 0,dp[0][j] = 0
2.对于每个物品i,从j = 1到j = V,正序枚举背包容量:
3.对于每个物品i,从j = w[i]到j = V,正序枚举背包容量:
4.对于每个物品i,从k = 0到k = min(v[i], j/w[i]),正序枚举物品数量:
5.dp[i][j] = max(dp[i][j], dp[i-1][j-k*w[i]]+k*v[i])
6.最终结果存储在dp[N][V]中
C++代码:
int dp[MAX_N][MAX_V]; // dp数组
int w[MAX_N], v[MAX_N]; // 物品的重量和价值
int N, V; // 物品数量和背包容量
int solve() {
memset(dp, 0, sizeof(dp)); // 初始化dp数组
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= V; j++) {
for (int k = 0; k <= min(v[i], j/w[i]); k++) {
dp[i][j] = max(dp[i][j], dp[i-1][j-k*w[i]]+k*v[i]);
}
}
}
return dp[N][V]; // 返回最终结果
}
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)