November
9th,
2017
Table of Contents
1. 01背包
问题描述：N件商品，M元现金，每件商品价格need[i]，价值val[i]，每件商品只能购买一次。如何购买使得总价值最高。
状态方程：设dp(i, j)为j元钱购买前n见商品能取得的最大价值。
空间优化：
for i = 0 .. N-1
for j = M .. need(i)
f(j) = max{f(j), f(j-need(i)) + val(i)}
C++代码：
int N, M;
int need[502]={0};
int val[502]={0};
int dp[100005]={0};
int main() {
cin >> N >> M;
for(int i=0; i<N; i++){
cin >> need[i];
cin >> val[i];
}
for(int i=0; i<N; i++)
for(int j=M; j>=need[i]; j--)
dp[j] = max(dp[j], dp[j-need[i]]+val[i]);
cout << dp[M];
}
2. 完全背包
问题描述：N件商品，M元现金，每件商品价格need[i]，价值val[i]，每件商品能购买多次。如何购买使得总价值最高。
状态方程：设dp(i, j)为j元钱购买前n见商品能取得的最大价值。
dp(i, j)与dp(i, j-need(i))有重复计算，可以优化
空间优化：
for i = 0 .. N-1
for j = need(i) .. M
f(j) = max{f(j), f(j-need(i)) + val(i)}
C++代码：
int N, M;
int need[502]={0};
int val[502]={0};
int dp[100005]={0};
int main() {
cin >> N >> M;
for(int i=0; i<N; i++){
cin >> need[i];
cin >> val[i];
}
for(int i=0; i<N; i++)
for(int j=need[i]; j<=M; j++){
dp[j] = max(dp[j], dp[j-need[i]]+val[i]);
}
cout << dp[M];
}
3. 状态压缩
问题描述：N个位置，每个位置有垃圾w[i]。清理垃圾时，连续M个位置最多清理Q个。求最多能清理多少垃圾。
思路：每个位置是否清理取决于前M个位置的具体情况，因此需要对前M个位置进行编码。假设由第i个位置向前依次为p1，p2……
状态方程：设dp(i, p1, ..., pM-1)为状态是p1, ..., pM-1的情况下最佳结果。
进一步的，可以将dp(i, p1, ..., pM-1)写成二进制串s