C语言中用动态规划法求解0-1背包问题 c=10,w:2 2 6 5 4,v:6 3 5 4 6
时间: 2024-04-07 22:30:03 浏览: 41
下面是根据您提供的物品重量和价值,使用动态规划算法求解0-1背包问题的C语言代码示例:
```c
#include <stdio.h>
// 定义最大物品数量和背包容量
#define MAX_N 100
#define MAX_W 1000
// 物品的重量和价值
int weight[MAX_N] = {0, 2, 2, 6, 5, 4};
int value[MAX_N] = {0, 6, 3, 5, 4, 6};
// 动态规划表格
int dp[MAX_N][MAX_W];
// 求解0-1背包问题
int knapsack(int n, int W) {
// 初始化第一行和第一列为0
for (int i = 0; i <= n; i++) {
dp[i][0] = 0;
}
for (int j = 0; j <= W; j++) {
dp[0][j] = 0;
}
// 填充动态规划表格
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
if (weight[i] <= j) {
// 当前物品的重量小于等于背包容量,可以选择放入或不放入背包
dp[i][j] = (value[i] + dp[i - 1][j - weight[i]]) > dp[i - 1][j] ? (value[i] + dp[i - 1][j - weight[i]]) : dp[i - 1][j];
} else {
// 当前物品的重量大于背包容量,只能选择不放入背包
dp[i][j] = dp[i - 1][j];
}
}
}
// 返回最优解
return dp[n][W];
}
int main() {
int n = 5; // 物品数量
int W = 10; // 背包容量
int max_value = knapsack(n, W);
printf("背包中物品的最大总价值为:%d\n", max_value);
return 0;
}
```
根据您提供的物品重量和价值数组,代码中将重量和价值数组初始化为`{0, 2, 2, 6, 5, 4}`和`{0, 6, 3, 5, 4, 6}`。运行上述代码,将输出背包中物品的最大总价值为`15`。
相关推荐
![](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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)