递归算法求01背包问题的完整c语言代码

以下是求解01背包问题的完整递归算法C语言代码：

#include <stdio.h> 

// 定义背包容量和物品个数 
#define N 5 
#define C 10 

// 物品重量和价值 
int w[N] = {2, 2, 6, 5, 4}; 
int v[N] = {6, 3, 5, 4, 6}; 

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

// 递归实现01背包问题 
int knapsack(int i, int j) { 
    if (i == N) { // 没有物品可以放置了 
        return 0; 
    } 
    if (j < w[i]) { // 当前物品放不下，尝试放下一个物品 
        return knapsack(i+1, j); 
    } else { // 可以放置该物品，需要比较放置和不放置的价值 
        return max(knapsack(i+1, j), knapsack(i+1,j-w[i]) + v[i]); 
    } 
} 

int main() { 
    int result = knapsack(0, C); 
    printf("01背包问题的最大价值为：%d\n", result); 
    return 0; 
} 

注意：此代码中未进行输入数据的操作，需要自己在代码中进行定义。另外，此代码为递归实现的01背包问题，不是最优解，仅供学习参考。

相关问题

用递归算法求解简单装载问题代码c语言

在C语言中，我们可以使用递归算法解决简单装载问题，比如经典的0-1背包问题。这是一个动态规划问题，其中物品有固定的价值和体积，目标是在不超过背包容量的前提下尽可能获取总价值最大的物品组合。

以下是一个简单的递归函数示例，用于求解背包问题：

#include <stdio.h>

// 定义物品结构体
typedef struct {
    int value; // 物品价值
    int weight; // 物品重量
} Item;

// 递归函数，动态规划策略
int knapsack(int W, Item items[], int n, int curr_weight) {
    if (n == 0 || curr_weight == 0) return 0; // 基本情况：没有物品或当前包已满
    if (items[n-1].weight <= curr_weight) { // 当前物品能完全放入
        return max(knapsack(W, items, n-1, curr_weight - items[n-1].weight) + items[n-1].value,
                   knapsack(W, items, n-1, curr_weight)); // 选择装入或不装入
    } else { // 当前物品无法全部放入，考虑不装入
        return knapsack(W, items, n-1, curr_weight);
    }
}

// 辅助函数，计算两个数的最大值
int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int W = 50; // 背包容量
    Item items[] = {{60, 10}, {100, 20}, {120, 30}}; // 物品数组
    int n = sizeof(items) / sizeof(items[0]);

    printf("最大价值: %d\n", knapsack(W, items, n, W));
    return 0;
}

背包问题C语言非递归算法程序

以下是背包问题的 C 语言非递归算法程序：

#include <stdio.h>

#define MAX_N 100 // 最大物品数量
#define MAX_W 1000 // 最大背包容量

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

int knapsack(int n, int w[], int v[], int W) {
    int dp[MAX_W + 1] = {0}; // 初始化为 0
    for (int i = 0; i < n; i++) {
        for (int j = W; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[W];
}

int main() {
    int n, W;
    int w[MAX_N], v[MAX_N];
    scanf("%d%d", &n, &W);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &w[i], &v[i]);
    }
    printf("%d\n", knapsack(n, w, v, W));
    return 0;
}

该算法使用动态规划思想，通过填表法求解背包问题，时间复杂度为 $O(nW)$，空间复杂度为 $O(W)$。