用C语言实现背包问题的函数
时间: 2024-05-14 20:15:12 浏览: 18
以下是一个基于动态规划的背包问题的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("Maximum value that can be put in a knapsack of capacity %d is %d\n", W, knapSack(W, wt, val, n));
return 0;
}
```
上述代码中,knapSack()函数接受四个参数:背包的容量W,物品的重量数组wt,物品的价值数组val,以及物品的数量n。该函数返回能够在背包容量为W时放置的最大价值。
函数中使用一个二维数组K来存储已经计算过的最优值。首先,将第一行和第一列初始化为0,表示当物品数量为0或者背包容量为0时,最大价值为0。然后,对于每个物品i和背包容量w,如果当前物品的重量wt[i-1]小于等于背包容量w,则有两种情况:1)将该物品放入背包,此时最大价值为val[i-1] + K[i-1][w-wt[i-1]];2)不将该物品放入背包,此时最大价值为K[i-1][w]。取两种情况的较大值作为当前状态的最大价值。如果当前物品的重量wt[i-1]大于背包容量w,则只能选择不将该物品放入背包,最大价值为K[i-1][w]。
在主函数中,我们给出了一个具体的例子,其中有三个物品,重量分别为10、20和30,价值分别为60、100和120,背包容量为50。程序输出了最大可以放入背包的价值,即220。
相关推荐
![](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)