0-1背包问题-526互联

写的很不错。但是动态数组的定义写得不如我下面：

这道题关键在于理解动态规划公式的定义：

可以定义一个二维数组dp[N][C+1]，N是物品的种类，C是背包的承重（或者体积）

dp[i][j]是这个数组的一个元素，其值就表示从前i件物品进行选择，在不超过容量j的前提下所满足最大的物品总价值。（注：此处的第i件物品对应与数组下标i）。

最核心的代码如下：

    /**
     *
     * @param N 物品数
     * @param C 背包容量
     * @param v 每件的体积
     * @param w 每件物品的价值
     * @return 最大价值
     */
    public int zoKnapsack(int N, int C, int[] v, int[] w) {
        //0-1背包朴素
        int[][] dp = new int[N][C+1];
        //初始化
        for (int j = 0; j <= C; j++) {
            dp[0][j] = j >= v[0] ? w[0] : 0;
        }

        //处理剩余元素
        for (int i = 1; i < N; i++) {
            for (int j = 0; j <= C; j++) {
                //不选
                int x = dp[i-1][j];
                //选
                int y = j >= v[i] ? dp[i-1][j-v[i]] + w[i] : 0;
                //取两者中的最大值
                dp[i][j] = Math.max(x, y);
            }
        }
        return dp[N-1][C];
    }

我的完整代码如下（测试可运行）：

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

#define MAX(x, y)    ((x)>(y))?(x):(y)
typedef struct
{
    int weight;
    int value;
}Bagobj;

int SolveBagProb(int N, int M, Bagobj *objlist);
int SolveBagProbPlus(int N, int M, Bagobj *objlist);
int SolveBagProbPlusPlus(int N, int M, Bagobj *objlist);

int main() {
    //输入数据
    int N = 0;
    int M = 0;
    
    //1. 物品的数量
    scanf("%d", &N);
    scanf("%d", &M);

    Bagobj *objlist = (Bagobj *)malloc(sizeof(Bagobj)*N);//使用动态数组
    for(int i=0; i<N; i++)
    {
        scanf("%d", &objlist[i].weight);
    }
    for(int i=0; i<N; i++)
    {
        scanf("%d", &objlist[i].value);
    }
    
    #if 1
    //int res = SolveBagProb(N, M, objlist);
    //int res = SolveBagProbPlus(N, M, objlist);
    int res = SolveBagProbPlusPlus(N, M, objlist);
    printf("%d", res);
    #endif
}

//解决背包问题：
//所需要的数据:物品种类N，背包承重M，每种物品的重量和价值(w,v)
//解法1
int SolveBagProb(int N, int M, Bagobj *objlist)
{
    //初始化一个动态规划数组，dp[N][M+1],初始化其第一行。
    //对于dp[i][j]而言：i是前i个物件，j是背包的承重(变)。
    int dp[N][M+1];
    for(int j=0; j<=M; j++)
    {
        //求价值，错误代码：dp[0][j] = (j>=objlist[0].weight)?(objlist[0].weight):(0);
        dp[0][j] = (j>=(objlist[0].weight))?(objlist[0].value):(0);
        //printf("dp[0][%d] = %d\n",j, dp[0][j]);
    }

    //对下面每一行[1, N-1],求动态规划式子
    int alt_full = 0;
    int alt_notfull = 0;
    for(int i=1; i<N; i++)
    {
        for(int j=0; j<=M; j++)
        {
            alt_full = dp[i-1][j];
            
            int temp_weight = objlist[i].weight;
            if(j >= temp_weight)
            {
                alt_notfull = dp[i-1][j-temp_weight]+objlist[i].value;
            }
            else {
                alt_notfull = 0;
            }
            dp[i][j] = MAX(alt_full, alt_notfull);
            //printf("dp[%d][%d] = %d\n",i,j, dp[i][j]);
        }
    }
    return dp[N-1][M];
}

//解法2
int SolveBagProbPlus(int N, int M, Bagobj *objlist)
{
    //初始化一个动态规划数组，dp[N][M+1],初始化其第一行。
    //对于dp[i][j]而言：i是前i个物件，j是背包的承重(变)。
    int dp[2][M+1];
    for(int j=0; j<=M; j++)
    {
        //求价值，下面这处错误
        //dp[0][j] = (j>=objlist[0].weight)?(objlist[0].weight):(0);
        dp[0][j] = (j>=(objlist[0].weight))?(objlist[0].value):(0);
        //printf("dp[0][%d] = %d\n",j, dp[0][j]);
    }

    //对下面每一行[1, N-1],求动态规划式子
    int alt_full = 0;
    int alt_notfull = 0;
    for(int i=1; i<N; i++)
    {
        for(int j=0; j<=M; j++)
        {
            alt_full = dp[(i-1)&0x01][j];

            int temp_weight = objlist[i].weight;
            if(j >= temp_weight)
            {
                //alt_notfull = dp[i-1][j-temp_weight]+temp_weight;
                alt_notfull = dp[(i-1)&0x01][j-temp_weight]+objlist[i].value;
            }
            else {
                alt_notfull = 0;
            }
            dp[i&0x01][j] = MAX(alt_full, alt_notfull);
            //printf("dp[%d][%d] = %d\n",i,j, dp[i][j]);
        }
    }
    return dp[(N-1)&0x01][M];
}
//解法3
int SolveBagProbPlusPlus(int N, int M, Bagobj *objlist)
{
    //初始化一个动态规划数组，dp[N][M+1],初始化其第一行。
    //对于dp[i][j]而言：i是前i个物件，j是背包的承重(变)。
    int dp[M+1];
    for(int j=0; j<=M; j++)
    {
        //求价值，下面这处错误
        //dp[0][j] = (j>=objlist[0].weight)?(objlist[0].weight):(0);
        dp[j] = (j>=(objlist[0].weight))?(objlist[0].value):(0);
        //printf("dp[0][%d] = %d\n",j, dp[0][j]);
    }

    //对下面每一行[1, N-1],求动态规划式子
    int alt_full = 0;
    int alt_notfull = 0;
    for(int i=1; i<N; i++)
    {
        for(int j=M; j>=0; j--)
        {
            alt_full = dp[j];

            int temp_weight = objlist[i].weight;
            if(j >= temp_weight)
            {
                //alt_notfull = dp[i-1][j-temp_weight]+temp_weight;
                alt_notfull = dp[j-temp_weight]+objlist[i].value;
            }
            else {
                alt_notfull = 0;
            }
            dp[j] = MAX(alt_full, alt_notfull);
            //printf("dp[%d][%d] = %d\n",i,j, dp[i][j]);
        }
    }
    return dp[M];
}