题解 | #01背包#

#define max(a, b) ((a) > (b) ? (a) : (b))
int knapsack(int V, int n, int** vw, int vwRowLen, int* vwColLen ) {
    int dp[V + 1];//定义一个数组有V+1个元素，值为从0到V，表示当体积为这些数时，相应可容纳的重量
    int vi, mi;    //定义某个物品的体积为vi，重量为mi
    for (int i = 0; i <= V; i++)
    {
        dp[i] = 0;   //先将数组值全部初始化为0
    }
    for (int i = 1; i <= n; i++)  //物品从第1个开始，到第n个，但数组下标是从0到n-1
    {
        //vw数组第一个维度表示第几个物品，第二个维度只有0和1，为0表示体积，为1表示重量
        vi = vw[i - 1][0]；//记录第i个物品的体积
        mi = vw[i - 1][1];  //记录第i个物品的重量
        for (int j = V; j >= vi; j--)    //j若小于某物品的重量vi，则一个物品都装不了
        {
            dp[j] = max(dp[j - vi] + mi, dp[j]);
            //dp[j - vi] 表示背包装了某物品之后还可承载物品的总重量
            //dp[j - vi] + mi 表示装了某物品的背包总共可承载的重量
           //dp[j] 表示可容纳体积为j的背包总共可承载的重量
          //max这句的意思就是比较装与不装某个物品，哪种情况可承载的物品更重
        }
    }
    return dp[V];
}