c语言动态规划完全背包问题不光求出最优值(即背包达到的最大价值),还要给出最优解(即每个物品装还是不装,输出xi最后取值)。解释代码并算出时间复杂度
时间: 2024-05-11 21:13:49 浏览: 5
下面是一个使用动态规划求解完全背包问题,并输出最优解的C语言代码:
```
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n, m; // 物品数量和背包容量
scanf("%d %d", &n, &m);
int w[n+1], v[n+1]; // 物品的重量和价值
for (int i = 1; i <= n; i++) {
scanf("%d %d", &w[i], &v[i]);
}
int dp[m+1]; // dp数组
int choice[n+1][m+1]; // 记录最优解的选择情况
for (int i = 0; i <= m; i++) {
dp[i] = 0;
choice[0][i] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = w[i]; j <= m; j++) {
if (dp[j] < dp[j-w[i]] + v[i]) {
dp[j] = dp[j-w[i]] + v[i];
choice[i][j] = 1; // 选择装第i个物品
} else {
choice[i][j] = 0; // 不选择装第i个物品
}
}
}
printf("%d\n", dp[m]); // 输出最优值
int x[n+1]; // 记录每个物品是否装入背包
for (int i = 1; i <= n; i++) {
x[i] = 0;
}
int j = m;
for (int i = n; i >= 1; i--) {
if (choice[i][j] == 1) {
x[i] = 1; // 第i个物品装入背包
j -= w[i];
}
}
for (int i = 1; i <= n; i++) {
printf("%d ", x[i]);
}
printf("\n");
return 0;
}
```
代码中,首先读入物品数量和背包容量,以及每个物品的重量和价值。然后定义一个dp数组和一个choice数组,分别用来记录最优值和最优解的选择情况。初始化dp数组和choice数组,然后进行动态规划求解。
在求解过程中,如果发现选择装第i个物品可以获得更大的价值,则更新dp数组和choice数组。
求解完毕后,输出最优值,并根据choice数组求出每个物品是否装入背包。最后输出每个物品的选择情况,即可得到最优解。
代码的时间复杂度为O(nm),其中n为物品数量,m为背包容量。