背包问题

一、01背包

dp[i][j]->第i个物品，放在背包里，总重量不超过j的前提下，所获得的最大价值。
状态转移方程
如果第i个物品大于所剩的容量ci>j,则不能放这个物品，最大值为之前的最大值。
dp[i][j]=dp[i-1][j]
如果第i个物品小于所剩容量 ci<j,这时可以选择放或者不放，放了则要选择之前为j-ci容量的背包，才能保证放了之后的总容量为j。dp[I][j]=max(dp[i-1][j],dp[i-1][j-ci]+wi).

for (int i = 1; i <= N; ++i) {
    for (int j = 0; j <= V; ++j) {
        if(j >= c[i]) {
            dp[i][j] = max(dp[i - 1][j - c[i]] + w[i], dp[i - 1][j]);
        } else {
            dp[i][j] = dp[i - 1][j];
        }
    }
}

01背包的空间优化

我们可以把dp数组只开成一维表示体积，然后从大到小的枚举体积，也就是从V到0枚举。
注意！！！01背包是从大到小枚举体积。
转移方程为：dp[j]=max(dp[j-ci]+wi,dp[j]).

for (int i = 1; i <= n; ++i)
    for (int j = v; j >= c[i]; --j) {
        dp[j] = max(dp[j - c[i]] + w[i], dp[j]);
    }

二、多重背包

每种物品有ni个
解法：在状态转移过程中枚举k，代表第i个物品的选取次数，将多重背包转换成01背包
dp[i][v]=max(dp[i][v],dp[i-1][v-kci]+kwi);

for (int i = 1; i <= N; i++) {
    for (int j = 0; j <= V; j++) {
        for (int k = 0; k <= n[i]; k++) {
            if (j >= c[i] * k) {
                dp[i][j] = max(dp[i - 1][j - c[i] * k] + w[i] * k, dp[i][j]);
            }
        }
    }
}

注意，当k=0时候，dp[i][j]=max(dp[i-1][j],dp[i][j]);相当于01背包中的else部分，选择放或者不放

多重背包的空间优化

多重背包可以转化为01背包，依然可以像01背包一样优化空间，依然按照从大到小的顺序枚举背包的体积。

for (int i = 1; i <= N; i++) {
    for (int j = V; j >= 0; j--) {
        for (int k = 1; k <= n[i]; k++) {
            if (j >= c[i] * k) {
                dp[j] = max(dp[j - c[i] * k] + w[i] * k, dp[j]);
            }
        }
    }
}

三、完全背包

每种物品的数量是无限的
解法：虽然每个物品的数量是无限的，但是背包的容量有限，可以根据背包的容量限制选取的数量，进而转换为多重背包问题，进而转化为01背包问题。

for (int i = 1; i <= N; i++) {
    for (int j = 0; j <= V; j++) {
        for (int k = 0; k * c[i] <= j; k++) {
            dp[i][j] = max(dp[i - 1][j - c[i] * k] + w[i] * k, dp[i][j]);
        }
    }
}

时间优化找规律发现
直接将01背包中的dp[i-1][j]换成dp[i][j];

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= v; j++) {
        if (j >= c[i]) {
            dp[i][j] = max(dp[i][j - c[i]] + w[i], dp[i - 1][j]);
        } else {
            dp[i][j] = dp[i - 1][j];
        }
    }
}

完全背包的空间优化

for (int i = 1; i <= n; i++) {
    for (int j = c[i]; j <= v; j++) {
        dp[j] = max(dp[j - c[i]] + w[i], dp[j]);
    }
}

与01背包相比，完全背包只是第二重循环的顺序发生了反转。

总结

记空间优化后的代码

//01 背包 就是从V开始枚举体积
//dp[j]=max(dp[j-c[i]]+w[i],dp[j]);
for (int i = 1; i <= n; ++i)
    for (int j = v; j >= c[i]; --j) {
        dp[j] = max(dp[j - c[i]] + w[i], dp[j]);
    }

//多重背包
//和01相同 从V开始枚举体积，在枚举体积之后，从k开始枚举选择当前物品的数量
dp[j]=max(dp[j-k*c[i]]+w[i]*k,dp[j])
for (int i = 1; i <= N; i++) {
    for (int j = V; j >= 0; j--) {
        for (int k = 1; k <= n[i]; k++) {
            if (j >= c[i] * k) {
                dp[j] = max(dp[j - c[i] * k] + w[i] * k, dp[j]);
            }
        }
    }
}

//完全背包
完全背包更简单，直接和01背包一样，只不过是从c[i]~V开始枚举体积
dp[j]=max(dp[j-c[i]]+w[i],dp[j]);
for (int i = 1; i <= n; i++) {
    for (int j = c[i]; j <= v; j++) {
        dp[j] = max(dp[j - c[i]] + w[i], dp[j]);
    }
}

使用背包解题时dp[0]初始化的三种情况

如果方案数，那 dp[0] = 1，代表着刚开始没装就 1 种方案
如果求最优解，那 dp[0] = 0，表示什么都没装就是 0
如果求是否可以，那 dp[0] = true，表示什么都没装就可以装到 0 位置