背包问题c语言
时间: 2023-07-07 07:08:15 浏览: 71
背包问题是一个经典的动态规划问题,可以用C语言实现。以下是一个基本的背包问题的C代码:
```c
#include<stdio.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int knapsack(int W, int wt[], int val[], int n) {
int i, w;
int K[n+1][W+1];
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i==0 || w==0)
K[i][w] = 0;
else if (wt[i-1] <= w)
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
else
K[i][w] = K[i-1][w];
}
}
return K[n][W];
}
int main() {
int val[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int W = 50;
int n = sizeof(val)/sizeof(val[0]);
printf("The maximum value that can be put in a knapsack of capacity %d is %d", W, knapsack(W, wt, val, n));
return 0;
}
```
这个程序使用了动态规划的思想来解决背包问题。其中,`val[]`和`wt[]`数组分别表示每个物品的价值和重量,`W`表示背包的容量,`n`表示物品的数量。在`knapsack`函数中,我们定义了一个二维数组`K`来保存每个子问题的解,然后使用一个嵌套的循环来计算每个子问题的解,并将其存储在`K`数组中。最后,返回`K[n][W]`即为整个问题的解。
上述代码只是一个简单的例子,实际应用中可能会有更复杂的要求和限制条件。但是使用类似的动态规划思想,可以解决各种不同类型的背包问题。