【Luogu】【关卡2-15】动态规划的背包问题（2017年10月）【还差一道题】

任务说明：这是最基础的动态规划。不过如果是第一次接触会有些难以理解。加油闯过这个坎。

01背包二维数组优化成滚动数组的时候有坑有坑有坑！！！必须要downto，downto，downto

情景和代码见装箱问题。

P1060 开心的金明

小明的妈妈给小明N元钱，小明想买m件物品，每个物品价值为 价格*重要度，求出不超过N元钱的情况下，最多能买多少价值的物品，输出价值。

解法：直接的01背包问题，我居然还去看了书。。递推方程一次写不出来。方程需要记忆。

dp[i][j]表示前i件物品总价格不超过j元的最大总价值。

需要学习下怎么在博客园输入latex公式orz。。。

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>

using namespace std;


int main() {
    int n, m;
    cin >> n >> m;
    int w[m][2];
    for (int i = 0; i < m; ++i) {
        cin >> w[i][0] >> w[i][1];
        w[i][1] *= w[i][0];
    }

    int dp[m+1][n+1];
    memset(dp, 0, sizeof(dp));

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

    return 0;
}

P1164 小A点菜

有M元， N种菜(每个菜只有一份)，每种菜有价格，求能把M元全花完的方案数。

解答：一开始全WA....哭死..其实还是经典的01背包问题。

一维的转移方程为： dp[j] += dp[j-price[i-1]]； 初始化条件为 dp[0] = 1, dp[1..m] = 0。 （因为需要花0元只有一种方案，就是啥也不买）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int dp[m+1] = {0};
    dp[0] = 1;
    int price[n];
    for (int i = 0; i < n; ++i) {
        cin >> price[i];
    }
    for(int i = 1; i <= n; ++i) {
        for (int j = m; j >= 0; --j) {
            if (j >= price[i-1]) {
                dp[j] = dp[j] + dp[j-price[i-1]];
            }
        }
    }
    cout << dp[m] << endl;
    return 0;
}

金明的预算方案

P1048 采药

就是01背包，裸的，直接写了，方程同P1060

提交一次AC

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

int main() {
    int T, M;
    cin >> T >> M;
    int w[M][2];
    for (int i = 0; i < M; ++i) {
        cin >> w[i][0] >> w[i][1];
    }
    int dp[M+1][T+1];
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= M; ++i) {
        for (int j = 1; j <= T; ++j) {
            if (j < w[i-1][0]) { dp[i][j] = dp[i-1][j]; }
            else {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1][0]] + w[i-1][1]);
            }
        }
    }
    cout << dp[M][T] << endl;
    return 0;
}

P1049 装箱问题

有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30，每个物品有一个体积（正整数）。 要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

就是求怎么样是用的空间最大。裸的01背包。优化成滚动数组的时候被坑了。

//写成滚动数组的时候，max(dp[j], dp[j-w[i-1]]+w[i-1]);如果是从左到右，那么dp[j-w[i-1]]是个已经被更新过的值。。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

int main() {
    int c, n;
    cin >> c >> n;
    int w[n+1];
    for (int i = 0; i < n; ++i) {
        cin >> w[i];
    }
    int dp[c+1] = {0};
    for (int i = 1; i <= n; ++i) {
        //滚动数组这么写的时候，max(dp[j], dp[j-w[i-1]]+w[i-1]);如果是从左到右，那么dp[j-w[i-1]]是个已经被更新过的值。。
        //for (int j = 1; j <= c; ++j) {
        for (int j = c; j >= 1 ; --j) {
            if (j < w[i-1]) { dp[j] = dp[j]; }
            else {
                dp[j] = max(dp[j], dp[j-w[i-1]]+w[i-1]);
            }
        }
    }
    cout << c - dp[c] << endl;
    return 0;
}

P1616 疯狂的采药

采药问题的升级版，不限制每种物品的个数。完全背包问题(每个物品无穷个)。

完全背包的解法就是01背包的downto的写法改成正着写...不过这不是重点。重点是理解为啥需要正着写。

提交一次AC了

#include <bits/stdc++.h>

using namespace std;

int main() {
    int T, M;
    cin >> T >> M;
    int w[M][2];
    for (int i = 0; i < M; ++i) {
        cin >> w[i][0] >> w[i][1];
    }
    int dp[T+1] = {0};
    for (int i = 1; i <= M; ++i) {
        for (int j = 1; j <= T; ++j) {
            if (j < w[i-1][0]) { continue; }
            else {
                dp[j] = max(dp[j], dp[j-w[i-1][0]]+w[i-1][1]);
            }
        }
    }
    cout << dp[T] << endl;
    return 0;
}