CF106C Buns（多重背包问题）

题意：
面包师Lavrenty打算用馅料做几个面包，然后把它们卖掉。
Lavrenty有n克面团和m种不同的馅料。馅料种类的下标从1到m，他知道他的第i种馅料剩下ai 克，做一个第i种馅料的面包，恰恰需要bi克的i种馅料和 ci 克的面团，同时这种面包可以卖di 块Tugrik。
他也可以做没有馅的面包。每个这样的面包需要c0克面团，可以卖d0块Tugrik。所以Lavrenty可以做任何数量的包子，用不同的馅料或者不用馅料，除非用完了面团和馅料。Lavrenty会扔掉烘培面包后剩下的所有多余材料。
求出Lavrenty可以赚取的Tugrik的最大数量。

思路：将问题转换为多重背包问题，将每种馅料打包成一共可以做成多少分（包括没有馅料的面包）

然后对每种（0-m）馅料进行选择

多重背包模板：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int w[MAXN];    // 重量 
int v[MAXN];    // 价值 
int s[MAXN];    // 物品数量 
int f[MAXN];    // f[i][j], j重量下前i个物品的最大价值 
int main() 
{
    int n;
    int m;  // 背包重量 
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) 
        cin >> w[i] >> v[i] >> s[i];

    for(int i = 1; i <= n; ++i)
        for(int j = m; j>=0; --j)   
            for(int k = 1; k <= s[i]; ++k) 
                if(j>=k*w[i])
                    f[j] = max(f[j], f[j-k*w[i]]+k*v[i]);

    cout << f[m] << endl;

    return 0;
}

本题代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int dp[maxn];
int s[maxn];// 物品数量 
int w[maxn];// 价值 
int v[maxn];// 体积 
int main() {
    int n, m, c0, d0;
    int x1, x2, x3, x4;
    cin >> n >> m >> v[0] >> w[0];
    s[0] = n; 
    for (int i = 1; i <= m; i++) {
        cin >> x1 >> x2 >> v[i] >> w[i];
        s[i] = x1 / x2; //可自制的馅料数量转换为物品的数量
    }
    int ans = 0;
    for (int i = 0; i <= m; i++) {
        for (int j = n; j >= 0; j--) {
            for (int k = 1; k <= s[i]; k++) {
                if (j >= k * v[i]) {
                    dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
                }
            }
        }
    }
    cout << dp[n] << endl;
    return 0;
}

二进制优化

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int dp[maxn];
int s[maxn];// 物品数量 
int w[maxn];// 价值 
int v[maxn];// 体积 
int main() {
    int n, m, c0, d0;
    int x1, x2, x3, x4;
    cin >> n >> m >> v[0] >> w[0];
    s[0] = n; 
    for (int i = 1; i <= m; i++) {
        cin >> x1 >> x2 >> v[i] >> w[i];
        s[i] = x1 / x2; 
    }
    int ans = 0;
    for (int i = 0; i <= m; i++) {
        for (int j = 1; j <= s[i]; s[i] -= j, j <<= 1) {
            for (int k = n; k >= j * v[i]; k--) {
                dp[k] = max(dp[k], dp[k - j * v[i]] + j * w[i]);
            }
        }
        for (int k = n; k >= s[i] * v[i]; k--) {
            dp[k] = max(dp[k], dp[k - s[i] * v[i]] + s[i] * w[i]);
        }
    }
    cout << dp[n] << endl;
    return 0;
}