01背包问题c语言实现

以下是01背包问题的C语言实现：

#include<stdio.h>
#define N 100
#define M 1000

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n, m, i, j;
    int w[N], v[N], f[M];
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++) {
        scanf("%d%d", &w[i], &v[i]);
    }
    for (i = 0; i <= m; i++) {
        f[i] = 0;
    }
    for (i = 1; i <= n; i++) {
        for (j = m; j >= w[i]; j--) {
            f[j] = max(f[j], f[j - w[i]] + v[i]);
        }
    }
    printf("%d\n", f[m]);
    return 0;
}

相关问题

01背包问题C语言实现

01背包问题是一个经典的动态规划问题，它的目标是在给定的一组物品中选择一些物品放入容量为C的背包中，使得背包中物品的总价值最大。C语言实现的01背包问题可以使用动态规划算法来解决。具体实现可以参考引用中的代码，其中使用了二维数组dp[i][j]来表示前i个物品放入容量为j的背包中所能获得的最大价值。在实现过程中，需要注意初始化dp数组和处理边界情况。同时，可以参考引用和引用中的递归公式来理解动态规划算法的思路。

分支限界法解决01背包问题c语言实现

好的，这里提供一个基于C语言的分支限界法解决01背包问题的实现。下面的代码实现了一个求解01背包问题的函数，函数的参数包括物品数目n、背包容量c、每个物品的重量w和价值v，以及函数返回的最大价值。代码中使用了一个结构体Item来表示每个物品，其中包含了物品的重量和价值。

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

typedef struct {
    int weight;
    int value;
} Item;

// 比较函数，按照每个物品的单位价值从大到小排序
int cmp(const void* a, const void* b) {
    Item* itemA = (Item*)a;
    Item* itemB = (Item*)b;
    double uA = (double)itemA->value / itemA->weight;
    double uB = (double)itemB->value / itemB->weight;
    if (uA > uB) {
        return -1;
    } else if (uA < uB) {
        return 1;
    } else {
        return 0;
    }
}

// 分支限界法求解01背包问题
double knapsack(int n, int c, int* w, int* v) {
    Item* items = (Item*)malloc(n * sizeof(Item));
    for (int i = 0; i < n; i++) {
        items[i].weight = w[i];
        items[i].value = v[i];
    }
    qsort(items, n, sizeof(Item), cmp);

    double maxV = 0.0;
    int curW = 0;
    int curV = 0;
    int* mark = (int*)calloc(n, sizeof(int));
    int* curMark = (int*)calloc(n, sizeof(int));
    double bound = 0.0;
    int k = 0;
    while (1) {
        if (curW + items[k].weight <= c) {
            curW += items[k].weight;
            curV += items[k].value;
            curMark[k] = 1;
        } else {
            curMark[k] = (c - curW) * 1.0 / items[k].weight;
            curW = c;
            curV += curMark[k] * items[k].value;
        }
        if (curV > maxV) {
            maxV = curV;
            for (int i = 0; i < n; i++) {
                mark[i] = curMark[i];
            }
        }
        if (k == n - 1) {
            break;
        }
        bound = curV + (c - curW) * (double)items[k + 1].value / items[k + 1].weight;
        if (bound <= maxV) {
            break;
        }
        k++;
    }

    free(curMark);
    free(mark);
    free(items);

    return maxV;
}

int main() {
    int n = 4;
    int c = 15;
    int w[] = {2, 3, 5, 7};
    int v[] = {10, 5, 15, 7};
    double maxV = knapsack(n, c, w, v);
    printf("Max value: %.1f\n", maxV);
    return 0;
}

在这个实现中，我们首先将所有物品按照单位价值从大到小排序，然后按照顺序依次选择物品，直到背包装满或者没有物品可选。在每一次选择物品的过程中，我们计算剩余物品的价值上限，如果这个上限已经小于当前最优解，就可以剪枝，不再扩展该节点。如果这个上限大于当前最优解，则继续扩展该节点，直到找到一个完整的解或者搜索完整棵树。

希望这个C语言实现的例子能够对您有所帮助。