动态规划0-1背包问题c
时间: 2023-11-08 12:05:49 浏览: 45
好的,关于动态规划0-1背包问题的C语言实现,可以参考以下代码:
```c
#include <stdio.h>
#define MAX_N 100
#define MAX_W 1000
int n, W;
int w[MAX_N], v[MAX_N];
int dp[MAX_N+1][MAX_W+1];
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
scanf("%d %d", &n, &W);
for (int i = 0; i < n; i++) {
scanf("%d %d", &w[i], &v[i]);
}
for (int i = n-1; i >= 0; i--) {
for (int j = 0; j <= W; 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]] + v[i]);
}
}
}
printf("%d\n", dp[0][W]);
return 0;
}
```
相关问题
动态规划0-1背包问题C语言
以下是使用动态规划解决0-1背包问题的C语言代码:
```c
#include <stdio.h>
// max函数用于求两个数的最大值
int max(int a, int b) {
return (a > b) ? a : b;
}
// 动态规划求解0-1背包问题
int knapsack(int W, int wt[], int val[], int n) {
int i, w;
int K[n+1][W+1];
// 填充K数组
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0) {
K[i][w] = 0;
}
else if (wt[i-1] <= w) {
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
}
else {
K[i][w] = K[i-1][w];
}
}
}
return K[n][W];
}
int main() {
int val[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int W = 50;
int n = sizeof(val)/sizeof(val[0]);
printf("最大价值为:%d", knapsack(W, wt, val, n));
return 0;
}
```
在这个例子中,我们有3个物品,它们的价值分别为60、100和120,它们的重量分别为10、20和30。我们有一个最大的重量限制为50。程序输出的结果应该是220,这意味着我们可以选择第一项和第三项物品,它们的价值总计为220。
动态规划法0-1背包问题c语言
下面是使用动态规划法解决 0-1 背包问题的 C 语言代码。其中,items[] 数组存储物品的重量和价值,weight[] 和 value[] 数组分别存储背包容量和价值。
```c
#include <stdio.h>
#define MAX_WEIGHT 100 // 背包最大容量
#define MAX_ITEMS 100 // 物品最大数量
int weight[MAX_ITEMS+1]; // 物品重量
int value[MAX_ITEMS+1]; // 物品价值
int dp[MAX_ITEMS+1][MAX_WEIGHT+1]; // 动态规划数组
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
int n; // 物品数量
int w; // 背包容量
printf("请输入物品数量和背包容量:");
scanf("%d%d", &n, &w);
printf("请输入每个物品的重量和价值:\n");
for (int i = 1; i <= n; i++) {
scanf("%d%d", &weight[i], &value[i]);
}
// 动态规划
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= w; j++) {
if (j < weight[i]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);
}
}
}
printf("最大价值为:%d\n", dp[n][w]);
return 0;
}
```
在上面的代码中,使用二维数组 dp[i][j] 存储前 i 个物品,容量为 j 时的最大价值。在动态规划过程中,如果当前物品的重量大于当前背包容量,那么最大价值就是前 i-1 个物品,容量为 j 时的最大价值。否则,最大价值就是前 i-1 个物品,容量为 j 时的最大价值和前 i-1 个物品,容量为 j-weight[i] 时的最大价值加上当前物品的价值中的较大值。最终,dp[n][w] 就是最大价值。