背包问题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)$。

相关问题

背包问题非递归算法程序

背包问题是一个经典的动态规划问题，可以使用非递归算法来解决。以下是一个使用动态规划的非递归算法程序：

def knapsack(W, wt, val, n):
    # 创建一个二维数组来存储子问题的最优解
    dp = [[0 for x in range(W+1)] for x in range(n+1)]
 
    # 填充dp数组
    for i in range(n+1):
        for w in range(W+1):
            if i==0 or w==0:
                dp[i][w] = 0
            elif wt[i-1] <= w:
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]],  dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
 
    return dp[n][W]

其中，W是背包的容量，wt是每个物品的重量数组，val是每个物品的价值数组，n是物品数量。程序首先创建一个二维数组dp，用于存储最优解。接着，程序使用两个for循环来填充dp数组。在填充过程中，程序检查当前物品是否可以放入背包中。如果可以放入，则程序选择放入或不放入当前物品，以获得最大的价值。最后，程序返回dp数组的最后一个元素，即为问题的最优解。

背包问题非递归算法伪代码

以下是背包问题的非递归算法伪代码：

knapsack(W, wt, val, n):
    // W: 背包容量，wt: 物品重量数组，val: 物品价值数组，n: 物品数量
    dp = 二维数组，大小为 (n+1) x (W+1)
    
    // 初始化 dp 数组
    for i = 0 to n:
        for w = 0 to W:
            if i == 0 or w == 0:
                dp[i][w] = 0
            else if wt[i-1] <= w:
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][W]

其中，`dp[i][w]` 表示在前 `i` 个物品中，背包容量为 `w` 的情况下所能获得的最大价值。`wt[i-1]` 和 `val[i-1]` 分别表示第 `i` 个物品的重量和价值，因为数组下标是从 0 开始的，所以需要减去 1。最终返回 `dp[n][W]`，表示在前 `n` 个物品中，背包容量为 `W` 的情况下所能获得的最大价值。