用c语言实现:0-1背包问题: 有n件物品和一个容量为c的背包。第i件物品的容量是w[i],价值是p[i]。求解将哪些物品装入背包可使价值总和最大。 四、实验步骤 1、理解算法思想和问题要求; 2、编程实现题目要求; 3、上机输入和调试自己所编的程序; 4、验证分析实验结果
时间: 2024-05-13 19:19:20 浏览: 12
以下是用 C 语言实现 0-1 背包问题的代码:
```c
#include <stdio.h>
#define MAX_N 100
#define MAX_C 1000
int n, c;
int w[MAX_N], p[MAX_N];
int dp[MAX_N + 1][MAX_C + 1];
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
scanf("%d%d", &n, &c);
for (int i = 0; i < n; i++) {
scanf("%d%d", &w[i], &p[i]);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= c; j++) {
if (j < w[i]) {
dp[i + 1][j] = dp[i][j];
} else {
dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + p[i]);
}
}
}
printf("%d\n", dp[n][c]);
return 0;
}
```
输入格式为:
```
n c
w[0] p[0]
w[1] p[1]
...
w[n-1] p[n-1]
```
输出为最大价值总和。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)