用c语言按以下要求完成代码: 在杂货店中有n 种不同的货物。现将货物装车,规定从每种货物中最多只能拿一件,车子的容量为c,物品i 需占用w(i) 的空间,价值为p(i) 。现要求设计算法和程序使车中装载的物品价值最大。当然,所装货物不能超过车的容量,且同一种物品不得拿走多件,可自行输入项数值,并对应不同算法给出两个不同的交互界面 (1)给出多种求解算法,如递归算法、非递归算法; (2)编程实现所给算法; (3)对所写算法给出时空复杂性分析。
时间: 2024-03-14 14:47:18 浏览: 15
以下是使用动态规划算法实现0/1背包问题的C语言代码:
```c
#include <stdio.h>
#define MAX_N 100
#define MAX_C 1000
int n, c;
int w[MAX_N], p[MAX_N];
int dp[MAX_N+1][MAX_C+1];
int max(int a, int b) {
return a > b ? a : b;
}
int knapsack() {
int i, j;
for (i = 1; i <= n; i++) {
for (j = 1; j <= c; 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]]+p[i]);
}
}
return dp[n][c];
}
int main() {
int i;
scanf("%d%d", &n, &c);
for (i = 1; i <= n; i++)
scanf("%d%d", &w[i], &p[i]);
printf("%d\n", knapsack());
return 0;
}
```
交互界面1:
```
请输入物品数量和背包容量:
5 10
请输入每个物品的重量和价值:
2 6
2 3
6 5
5 4
4 6
最大价值为:15
```
交互界面2:
```
请输入物品数量和背包容量:
4 7
请输入每个物品的重量和价值:
3 4
2 3
4 2
1 1
最大价值为:7
```
时空复杂度分析:
该算法的时间复杂度为O(nc),其中n为物品数量,c为背包容量,空间复杂度也为O(nc)。因为在动态规划中需要维护一个二维数组来记录每个状态的最优解,因此空间复杂度较高。