现有n种物品,对1<=i<=n,第i种物品的重量为正整数w i ,价值为正整数p i ,背包能承受的最大载重量为正整数M,要求找出这n种物品的一个子集,使得子集中物品的总重量不超过M且总价值尽量大。0/1背包问题要求物品或者整件装入背包中,或者根本不装入(即不能装入物品的一部分),所以x i 限定只能取值0或1。 输入格式: 第1行是M和n,表示背包容量为M且有n件物品; 第2行是这n件物品的重量w i ; 第3行是各物品的价值p i ,背包容量和物品重量都为整数。 输出格式: 第1行是所选物品的价值之和,以及重量之和; 第2行是各物品装入背包的量,即x i 值。请用c语言代码实现
时间: 2024-03-18 08:39:12 浏览: 31
好的,下面是C语言的代码实现,使用动态规划求解0/1背包问题:
```c
#include <stdio.h>
#include <stdlib.h>
#define max(a,b) ((a)>(b)?(a):(b))
int main()
{
int M, n;
scanf("%d%d", &M, &n);
int *w = (int*)malloc(sizeof(int) * (n+1));
int *p = (int*)malloc(sizeof(int) * (n+1));
for(int i = 1; i <= n; ++i)
scanf("%d", &w[i]);
for(int i = 1; i <= n; ++i)
scanf("%d", &p[i]);
int **dp = (int**)malloc(sizeof(int*) * (n+1));
for(int i = 0; i <= n; ++i)
dp[i] = (int*)malloc(sizeof(int) * (M+1));
for(int i = 0; i <= M; ++i)
dp[0][i] = 0;
for(int i = 1; i <= n; ++i)
{
for(int j = 0; j <= M; ++j)
{
if(j < w[i])
dp[i][j] = dp[i-1][j];
else
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + p[i]);
}
}
printf("%d %d\n", dp[n][M], M);
int *x = (int*)malloc(sizeof(int) * (n+1));
for(int i = n; i >= 1; --i)
{
if(dp[i][M] > dp[i-1][M])
{
x[i] = 1;
M -= w[i];
}
else
x[i] = 0;
}
for(int i = 1; i <= n; ++i)
printf("%d ", x[i]);
printf("\n");
free(w);
free(p);
free(x);
for(int i = 0; i <= n; ++i)
free(dp[i]);
free(dp);
return 0;
}
```
代码中使用了动态规划的思想,首先动态申请了二维数组dp来表示状态,其中dp[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值。然后按照状态转移方程进行递推,最后回溯求解最优解。
注意,代码中使用了动态申请内存的方式,使用完毕后需要记得释放。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)