求解0/1背包问题动态规划c语言
时间: 2023-09-20 16:11:43 浏览: 90
用动态规划法求解0/1背包问题
0/1背包问题是一个经典的动态规划问题,其问题描述为:有n个物品和一个容量为V的背包,每个物品有一个重量w和一个价值v。要求从这些物品中选择一些装入背包中,使得装入背包中的物品重量不超过背包容量,且总价值最大。
下面是使用动态规划算法求解0/1背包问题的C语言代码:
```c
#include <stdio.h>
#define MAXN 1000 //最大物品个数
#define MAXV 1000 //最大背包容量
int w[MAXN], v[MAXN]; //物品的重量和价值
int dp[MAXV+1]; //记录背包容量为i时的最大总价值
int max(int a, int b)
{
return (a > b) ? a : b;
}
int main()
{
int n, V, i, j;
//读入物品个数和背包容量
printf("请输入物品个数和背包容量:");
scanf("%d %d", &n, &V);
//读入每个物品的重量和价值
printf("请输入每个物品的重量和价值:\n");
for (i = 1; i <= n; i++)
scanf("%d %d", &w[i], &v[i]);
//动态规划求解
for (i = 1; i <= n; i++)
{
for (j = V; j >= w[i]; j--)
{
dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
}
}
//输出结果
printf("背包能够装载的最大价值为:%d\n", dp[V]);
return 0;
}
```
其中,dp[i]表示背包容量为i时的最大总价值。在动态规划求解时,对于每个物品i,从背包容量V开始倒序遍历,若j≥w[i],则有dp[j]=max(dp[j], dp[j-w[i]]+v[i]),即当前背包容量下的最大总价值等于选择不装入物品i的最大总价值dp[j]和选择装入物品i的最大总价值dp[j-w[i]]+v[i]中的较大值。最终,dp[V]即为背包能够装载的最大价值。
阅读全文