01背包问题动态规划生成c语言代码

下面是01背包问题动态规划生成C语言代码的示例：

#include <stdio.h>
#define MAX_N 100
#define MAX_W 10000

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 = 0; i < n; i++) {
        for (int j = 0; j <= W; 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]] + v[i]);
            }
        }
    }

    printf("%d\n", dp[n][W]);

    return 0;
}

相关问题

回溯法求解0/1背包问题c语言代码生成

以下是使用回溯法求解0/1背包问题的C语言代码：

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define MAX_N 100  // 物品的最大数量

int N;  // 物品的数量
int W[MAX_N], V[MAX_N];  // 物品的重量和价值
int C;  // 背包的容量
int max_value;  // 最大价值
bool used[MAX_N];  // 记录背包中是否装入某个物品

// 回溯函数
void dfs(int i, int w, int v) {
    if (i == N) {  // 达到叶子节点
        if (w <= C && v > max_value) {  // 更新最大价值
            max_value = v;
            for (int j = 0; j < N; j++) {
                used[j] = false;
                if (w + W[j] <= C) {  // 记录背包中装入的物品
                    used[j] = true;
                }
            }
        }
        return;
    }
    dfs(i+1, w, v);  // 不装入第i个物品
    dfs(i+1, w+W[i], v+V[i]);  // 装入第i个物品
}

int main() {
    scanf("%d%d", &N, &C);
    for (int i = 0; i < N; i++) {
        scanf("%d%d", &W[i], &V[i]);
    }
    memset(used, false, sizeof(used));  // 初始化
    max_value = 0;
    dfs(0, 0, 0);  // 从第0个物品开始装
    printf("Max value: %d\n", max_value);
    printf("Items: ");
    for (int i = 0; i < N; i++) {
        if (used[i]) {
            printf("%d ", i);
        }
    }
    printf("\n");
    return 0;
}

该代码使用dfs函数进行回溯，枚举所有的物品装或不装的情况，并更新最大价值和记录背包中装入的物品。在主函数中，从标号为0的物品开始装，输出最大价值和装入的物品。

用动态规划解决复杂01背包问题C语言代码，要求随机生成十万个物品重量价值，用户输入背包容量后能输出最大价值

以下是用动态规划解决复杂01背包问题的C语言代码，其中通过rand()函数随机生成十万个物品的重量和价值，用户输入背包容量后能输出最大价值。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 100000
#define MAX_CAP 1000000

int weight[N];
int value[N];
int dp[MAX_CAP];

int main()
{
    int n, cap, i, j;
    srand(time(NULL));
    n = N;
    cap = MAX_CAP;
    for(i = 0; i < n; i++)
    {
        weight[i] = rand() % 100 + 1;
        value[i] = rand() % 1000 + 1;
    }

    for(i = 0; i < n; i++)
    {
        for(j = cap; j >= weight[i]; j--)
        {
            dp[j] = dp[j] > (dp[j - weight[i]] + value[i]) ? dp[j] : (dp[j - weight[i]] + value[i]);
        }
    }

    printf("请输入背包容量：\n");
    scanf("%d", &cap);
    printf("最大价值为：%d\n", dp[cap]);
    return 0;
}

其中，srand()函数用于初始化随机数种子，从而使每次运行时生成的随机数序列不同。在循环中，weight数组和value数组使用rand()函数生成随机数，并且范围分别为[1,100]和[1,1000]。最终，用户输入的背包容量cap即为所求的最大价值。