01背包问题c语言代码

#include<stdio.h>
#define MAXN 1000
#define MAXM 1000

int n,m;
int w[MAXN],v[MAXN];
int f[MAXM];

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

int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&w[i],&v[i]);
}
for(int i=1;i<=n;i++)
{
for(int 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语言为例：

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

int knapsack_01(int n, int C, int w[], int v[]) {
    // 定义一个二维数组用于保存状态
    int **dp = (int **)malloc((n+1) * sizeof(int *));
    for (int i = 0; i <= n; i++) {
        dp[i] = (int *)malloc((C+1) * sizeof(int));
    }
    // 初始化状态
    for (int j = 0; j <= C; j++) {
        dp[0][j] = 0;
    }
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= C; j++) {
            if (j >= w[i-1]) {
                dp[i][j] = (dp[i-1][j] > dp[i-1][j-w[i-1]]+v[i-1]) ? dp[i-1][j] : dp[i-1][j-w[i-1]]+v[i-1];
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    // 返回最终状态
    int res = dp[n][C];
    // 释放动态分配的内存
    for (int i = 0; i <= n; i++) {
        free(dp[i]);
    }
    free(dp);
    return res;
}

int main() {
    int n = 5;
    int C = 10;
    int w[] = {2, 2, 6, 5, 4};
    int v[] = {6, 3, 5, 4, 6};
    int res = knapsack_01(n, C, w, v);
    printf("The maximum value is %d.\n", res);
    return 0;
}

其中，n表示物品数量，C表示背包容量，w和v分别表示物品的重量和价值。在代码中，我们首先动态分配一个n+1行、C+1列的二维数组dp，用于保存状态。然后，我们初始化第0行的状态为0，表示在前0个物品中选择若干个物品放入容量为j的背包中所能获得的最大价值为0。接下来，我们利用状态转移方程，计算出dp[i][j]的值，最后返回dp[n][C]，即在前n个物品中选择若干个物品放入容量为C的背包中所能获得的最大价值。最后，我们释放动态分配的内存。

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

以下是动态规划01背包问题的C语言代码实现：

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

int w[N], v[N], dp[N][C];

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

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

其中，数组w和v分别表示物品的重量和价值，数组dp表示状态转移方程中的二维数组。在代码中，使用两层循环遍历所有的物品和容量，根据状态转移方程更新dp数组。最终的结果即为dp[n][c]。