洛谷 P3985 不开心的金明

洛谷 P3985 不开心的金明

该解法为：先求出所有商品的最小价格，看最小价格(minv)是否大于300。如果小于等于300，那么认为背包大小为30000，做01背包。如果大于300，认为取物品的数量固定为 w / m i n v w/minv w/minv，取价值最高的 w / m i n v w/minv w/minv个商品。

洛谷题解中很多人都使用这种解法，但实际上这种解法是不严谨的，或者说就是错的。
本解法思路为：由于n最大值为100，最多可以买100件物品。
证明：
记这些物品的最小价格为minv，由于价格的极差是3，那么最高价格可能为minv+3。
假设W元钱都买最小价格商品，最多购买 ⌊ W m i n v ⌋ lfloor frac{W}{minv} rfloor ⌊minvW​⌋。如果都买最大价格商品，最多购买 ⌊ W m i n v + 3 ⌋ lfloor frac{W}{minv+3} rfloor ⌊minv+3W​⌋，无论买哪种商品，购买数量最大都为100。
存在情况，如果所有的钱都买最小价格商品，相比购买最大价格商品省下的钱也无法再购买一个最小价格商品。那么在这种情况下，用W元钱能够购买的最大、最小价格商品的数量是相等的。
即 ⌊ W m i n v ⌋ = ⌊ W m i n v + 3 ⌋ ≤ 100 lfloor frac{W}{minv} rfloor =lfloor frac{W}{minv+3} rfloor le 100 ⌊minvW​⌋=⌊minv+3W​⌋≤100

记 W m i n v = k frac{W}{minv} = k minvW​=k，则 W = k ⋅ m i n v W=kcdot minv W=k⋅minv，

那么 W m i n v + 3 frac{W}{minv+3} minv+3W​ = k ⋅ m i n v m i n v + 3 = k ⋅ m i n v + 3 k − 3 k m i n v + 3 = k − 3 k m i n v + 3 frac{kcdot minv}{minv+3}=frac{kcdot minv+3k-3k}{minv+3}=k-frac{3k}{minv+3} minv+3k⋅minv​=minv+3k⋅minv+3k−3k​=k−minv+33k​

由于 ⌊ W m i n v ⌋ = ⌊ k ⌋ ≤ 100 lfloor frac{W}{minv} rfloor = lfloor k rfloor le 100 ⌊minvW​⌋=⌊k⌋≤100，k的值最大可以逼近101，即 k < 101 k<101 k<101

⌊ W m i n v ⌋ = ⌊ W m i n v + 3 ⌋ lfloor frac{W}{minv} rfloor =lfloor frac{W}{minv+3} rfloor ⌊minvW​⌋=⌊minv+3W​⌋相当于 ⌊ k ⌋ = ⌊ k − 3 k m i n v + 3 ⌋ lfloor k rfloor= lfloor k-frac{3k}{minv+3} rfloor ⌊k⌋=⌊k−minv+33k​⌋，右侧减去的数字一定要小于1。

所以： 3 k m i n v + 3 < 1 frac{3k}{minv+3} < 1 minv+33k​<1，化简得 m i n v + 3 3 > k frac{minv+3}{3}>k 3minv+3​>k，由于k最大可以逼近101，所以 m i n v + 3 3 ≥ 101 > k frac{minv+3}{3}ge 101 > k 3minv+3​≥101>k，得 m i n v ≥ 300 minv ge 300 minv≥300

整个推导看似天衣无缝，实际上是由 ⌊ W m i n v ⌋ = ⌊ W m i n v + 3 ⌋ ≤ 100 lfloor frac{W}{minv} rfloor =lfloor frac{W}{minv+3} rfloor le 100 ⌊minvW​⌋=⌊minv+3W​⌋≤100推出了 m i n v ≥ 300 minv ge 300 minv≥300。
m i n v ≥ 300 minv ge 300 minv≥300只是 ⌊ W m i n v ⌋ = ⌊ W m i n v + 3 ⌋ lfloor frac{W}{minv} rfloor =lfloor frac{W}{minv+3} rfloor ⌊minvW​⌋=⌊minv+3W​⌋的必要条件而非充分条件。

所以不能说在 m i n v ≥ 300 minv ge 300 minv≥300的情况下一定有 ⌊ W m i n v ⌋ = ⌊ W m i n v + 3 ⌋ lfloor frac{W}{minv} rfloor =lfloor frac{W}{minv+3} rfloor ⌊minvW​⌋=⌊minv+3W​⌋。

实际上，如果W能够整除minv，那么一定有 ⌊ W m i n v + 3 ⌋ < ⌊ W m i n v ⌋ lfloor frac{W}{minv+3} rfloor < lfloor frac{W}{minv} rfloor ⌊minv+3W​⌋<⌊minvW​⌋，无论minv的值有多大，都会产生这种情况。

这里给一组测试数据，
输入：

3 604 
302 400 
303 700 
302 400

正解应该是买两个302元的物品，得到的满意度应该是800。但如果使用本错误解法，得到的输出是700。

本题物品数量很小( N ≤ 100 Nle 100 N≤100)，而背包大小很大( W ≤ 1 0 9 W le 10^9 W≤109)，所以这里要尽量减小可以使用的背包大小。如果直接使用01背包的方法做，空间复杂度过高。
每个物品的价格的极差为3，记所有物品的最小价格为minv，那么可能的价格有：minv, minv+1, minv+2, minv+3。
如果每个物品价格很高，占用的背包空间就会很大，空间复杂度就很大。这里可以把每个物品的价格都减去minv，使得所有物品的价格只可能为0,1,2,3。购买这样处理后的物品最多100个，能花的钱最多为所有物品价格的加和sumv，这个加和一定小于等于300。在这种情况下，就可以认为背包大小为所有物品处理后价格的加和sumv，这个值不超过300。
而选择的商品的总花费仍受到总钱数W的限制。假设购买价格处理后商品的花费（即背包大小）为j，买了k个商品。这k个商品每个商品的基础花费为minv，多出的价格部分即为处理后的商品，通过j元购买，总花费可以认为是 k ∗ m i n v + j k*minv+j k∗minv+j，这个总花费不能超过W元，所以有 k ∗ m i n v + j ≤ W k*minv+jle W k∗minv+j≤W。这里涉及到了购买商品的数量，所以在状态定义时得包含商品数量这一项。

集合：购买商品的方案
限制：前几个商品中选择，最多花费，购买商品的数量
属性：重要度加和
条件：最大
统计量：重要度加和
状态定义：dp[i][j][k]：处理价格后，最多花费j元在前i个物品中选择物品购买，选了k个物品能获得的最大重要度加和。

记p[i]为第i物品的价格，c[i]为第i物品的重要程度。
集合：最多花费j元在前i个物品中选择物品购买，选了k个物品的方案
分割集合：第i物品是否选择

• 如果不选择第i物品，或无法选择第i物品，那么接下来需要用j元钱在前i-1个物品中购买k个物品。d[i][j][k] = dp[i-1][j][k]
• 如果第i物品满足 j ≥ p [ i ] jge p[i] j≥p[i]且k与j满足 k ∗ m i n v + j ≤ W k*minv+jle W k∗minv+j≤W，此时可以选择第i物品，共选择k个物品。如果选择第i物品，那么接下来需要用j-p[i]的元钱在前i-1个物品中购买k-1个物品。dp[i][j][k] = dp[i-1][j-p[i]][k-1]+c[i]
• 以上两种情况取最大值。

对于所有可能的k与j构成的数对，都会产生一个最大花费钱数（背包大小），在该值的限制下可以得到一个可以购买商品的最大价值。
应该遍历所有的k与j，求在前n个物品中选择物品，选择k个物品，j元购买价格处理后的商品，能获得的最大价值。即dp[n][j][k]的最大值。
这也相当于求dp数组中所有元素的最大值，这就是本题的结果。
该题可以进行滚动数组优化

#include
using namespace std;
#define N 105
#define M 305
#define INF 0x3f3f3f3f
int p[N], c[N];//p[i]:第i物品的价格 c[i]:第i物品的重要程度 
int dp[N][M][N];//dp[i][j][k]:处理价格后，最多j元在前i个物品中选择物品购买，选了k个物品能获得的最大重要度 
int n, w, minv = INF, sumv, ans;//sumv:处理后背包大小 
int main()
{
    cin >> n >> w;
    for(int i = 1; i <= n; ++i)
    {
        cin >> p[i] >> c[i];
        minv = min(minv, p[i]);
    }
    for(int i = 1; i <= n; ++i)
    {
        p[i] -= minv;
        sumv += p[i];
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j <= sumv; ++j)
        {
            for(int k = 1; k <= n; ++k)
            {
                if((long long)minv*k+j <= w && j >= p[i])
                    dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-p[i]][k-1]+c[i]);
                else
                    dp[i][j][k] = dp[i-1][j][k];
            }
        }
    for(int j = 0; j <= sumv; ++j)
        for(int k = 1; k <= n; ++k)
            ans = max(ans, dp[n][j][k]);
    cout << ans;
    return 0;
}

#include
using namespace std;
#define N 105
#define M 305
#define INF 0x3f3f3f3f
int p[N], c[N];//p[i]:第i物品的价格 c[i]:第i物品的重要程度 
int dp[M][N];//dp[i][j][k]:(i被优化掉)处理价格后，最多j元在前i个物品中选择物品购买，选了k个物品能获得的最大重要度 
int n, w, minv = INF, sumv, ans;//sumv:处理后背包大小 
int main()
{
    cin >> n >> w;
    for(int i = 1; i <= n; ++i)
    {
        cin >> p[i] >> c[i];
        minv = min(minv, p[i]);
    }
    for(int i = 1; i <= n; ++i)
    {
        p[i] -= minv;
        sumv += p[i];
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = sumv; j >= p[i]; --j)
        {
            for(int k = n; k >= 1; --k)
            {
                if((long long)minv*k+j <= w)
                    dp[j][k] = max(dp[j][k], dp[j-p[i]][k-1]+c[i]);
            }
        }
    }
    for(int j = 0; j <= sumv; ++j)
        for(int k = 1; k <= n; ++k)
            ans = max(ans, dp[j][k]);
    cout << ans;
    return 0;
}