帮我写个c语言的0-1背包问题的代码
时间: 2023-03-29 10:03:42 浏览: 81
0-1背包问题 (C语言编写)
好的,以下是-1背包问题的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 = ; i <= n; i++) {
for (w = ; w <= W; w++) {
if (i == || w == )
K[i][w] = ;
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[]);
printf("Maximum value: %d\n", knapsack(W, wt, val, n));
return ;
}
```
这个代码实现了-1背包问题,其中val数组表示每个物品的价值,wt数组表示每个物品的重量,W表示背包的最大承重,n表示物品的数量。函数knapsack返回背包能够承载的最大价值。
阅读全文