ala的杂货店

参考：

• https://blog.csdn.net/Choi_John/article/details/107311328
• https://blog.csdn.net/Choi_John/article/details/107345824

ala 的杂货店（第二天）

ala 的杂货店（第二天）

问题

Description 开张的第二天，dzl 再次带着 m 元钱来找 ala，ala 从新拿出了他准备的 n 件物品，每件物品有一个实用值和对应的价格，dzl 想在 m 元钱内买到实用值最多的物品组合。这次由于 ala 拿出的物品比昨天多，所以 dzl 可以很轻松的计算出来。dzl 急着去找女朋友，就想让你帮他解决这个问题。 Input 数据的第一行有两个整数，分别为 n 件物品和 m 元钱 (1⇐n⇐1000，1⇐m⇐1000) 第 i+1 行为第 i 件物品的实用值 c[i] 和价格 w[i] 元 (1⇐c[i],w[i]⇐1000) Output 输出一行为可以得到的最大的实用值。 Sample Input Copy 5 10 1 5 2 4 3 3 4 2 5 1 Sample Output Copy 14

解法

很典型的 0-1 背包问题，枚举 0~m 元可以买到的最多实用值

/** ala store: 0-1背包 */
int alaStoreII(vector<int>& c, vector<int>& w, int m) {
    int n = c.size();
    vector<int> dp(m + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int j = m; j > 0; j--) {
            if (j >= w[i]) {
                dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
            }
        }
    }
    return dp[m];
}

ala 的杂货店（第三天）

问题

Description 开张的第三天，dzl 气势汹汹地带着 m 元钱来找 ala，ala 这次不打算为难他，拿出的 n 种物品中每种物品有一个对应的价格，dzl 想知道花光 m 元钱可以购买的物品方案总数。今天可算是难住 dzl 了，想让你再次帮他解决这个问题。 Input 数据为单组 数据的第一行有两个整数，分别为 n 件物品和 m 元钱 (1⇐n⇐200，1⇐m⇐200) 第 i 行为第 i 种物品的价格 w[i] 元 (1⇐w[i]⇐200) 数据保证没有两种物品价格重复 Output 输出一行为可以购买的方案总数 Sample Input Copy 3 5 1 2 3 Sample Output Copy 5 HINT 样例中可以购买的方案分别为 [2,3]，[1,1,3]，[1,1,1,2]，[1,2,2]，[1,1,1,1,1]。

解法

完全背包问题，本质和 零钱兑换问题 一样，枚举 0~m 元可以买的物品方案总数

int alaStoreIII(vector<int>& w, int m) {
    // 完全背包问题，枚举0~m元对应的最大方案数
    int n = w.size();
    vector<int> dp(m + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j >= w[i]) {
                dp[j] = dp[j] + dp[j - w[i]];
            }
        }
    }
    return dp[m];
}