用C语言编写: 0-1背包问题。假设你有一个背包,最多能承重C千克,这里有k个物品,其重量分别为w1、w2、……、wk,在背包所能承受的重量下,尽可能得使背包里的物品重量最大。 void bag( int ball[], int n, int w)
时间: 2024-11-06 14:15:30 浏览: 3
在C语言中,我们可以使用动态规划(Dynamic Programming)的方法来解决0-1背包问题。这里是一个简单的`bag`函数实现,它接收一个整数数组`ball`表示每个物品的价值,`n`表示物品的数量,以及`w`表示背包的最大容量:
```c
#include <stdio.h>
// 动态规划函数,返回在给定背包容量下的最大价值
int knapsack(int ball[], int n, int w) {
// 初始化一个二维数组dp[n+1][w+1],其中dp[i][j]表示前i个物品可以达到的最大价值,背包容量为j
int dp[n + 1][w + 1];
// 遍历所有物品和背包容量
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= w; ++j) {
// 如果当前物品太大,无法放入背包
if (ball[i - 1] > j)
dp[i][j] = dp[i - 1][j]; // 不放这件物品
else { // 否则,选择放和不放,取较大价值
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - ball[i - 1]] + ball[i - 1]);
}
}
}
return dp[n][w];
}
// 辅助函数用于获取两个整数的最大值
int max(int a, int b) {
return a > b ? a : b;
}
// 示例调用
int main() {
int ball[] = {60, 100, 120}; // 物品价值
int n = sizeof(ball) / sizeof(ball[0]); // 物品数量
int w = 50; // 背包容量
int result = knapsack(ball, n, w);
printf("在背包容量为%d的情况下,最大总价值为%d\n", w, result);
return 0;
}
```
阅读全文