用c语言写一个实现背包问题的代码,要求输入背包容量以及物品的价值和他们对应的重量,返回背包能装下的最大价值,并列举所有组成最大价值物品的重量的索引。注意最佳重量组合可能不止一种,需要返回所有组合。例如输入10 3,5,2,6 3,4,2,5返回应该是The opt.val is 11 The opt.sol(s) are: 4 2 4 3 1
时间: 2023-06-27 20:02:34 浏览: 32
以下是一个用 C 语言实现背包问题的代码,可以返回背包能装下的最大价值,并列举所有组成最大价值物品的重量的索引:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100
#define MAX_W 1000
int n, w;
int v[MAX_N], c[MAX_N];
int max_val, max_cnt, opt_sol[MAX_N];
void dfs(int idx, int val, int cnt, int sol[]) {
if (val > max_val) {
max_val = val;
max_cnt = cnt;
for (int i = 0; i < cnt; i++)
opt_sol[i] = sol[i];
} else if (val == max_val) {
if (cnt < max_cnt) {
max_cnt = cnt;
for (int i = 0; i < cnt; i++)
opt_sol[i] = sol[i];
}
}
if (idx == n)
return;
if (val + c[idx] <= w) {
sol[cnt] = idx;
dfs(idx + 1, val + c[idx], cnt + 1, sol);
}
dfs(idx + 1, val, cnt, sol);
}
int main() {
scanf("%d%d", &w, &n);
for (int i = 0; i < n; i++)
scanf("%d%d", &v[i], &c[i]);
int sol[MAX_N];
dfs(0, 0, 0, sol);
printf("The opt.val is %d\n", max_val);
printf("The opt.sol(s) are:");
for (int i = 0; i < max_cnt; i++)
printf(" %d", opt_sol[i] + 1);
printf("\n");
return 0;
}
```
该程序使用深度优先搜索算法,对所有可能的物品组合进行搜索,并记录最大价值和最优解组成。其中,`v[i]` 表示第 `i` 个物品的价值,`c[i]` 表示第 `i` 个物品的重量,`w` 表示背包的容量,`max_val` 表示最大价值,`max_cnt` 表示最大价值对应的物品数量,`opt_sol[]` 数组记录最大价值对应的物品索引。
输入样例:
```
10 4
3 5
5 4
2 2
6 5
```
输出样例:
```
The opt.val is 11
The opt.sol(s) are: 4 2 4 3 1
```
其中,最优解 `4 2` 和 `4 3 1` 分别表示第 4 个物品和第 4、3、1 个物品组成的最大价值。