【题解】p1964 【mc生存】卖东西

#include <bits/stdc++.h>
using namespace std;
struct data{
 int w;
   int v;
   int c;
   string s;
}a[105] , b[134405];//a是原数组，b是用来处理的数组（具体看下面）
int n , m , t = 0 , x = 21 , f[22];
int main()
{
  cin >> m >> n;//输入
   x -= m;//除去不能卖的东西剩下的格子
   for(int i = 1; i <= n; i++)
       {
            cin >> a[i].w >> a[i].v >> a[i].c >> a[i].s;//输入
         for(int j = 1; j < i; j++)//如果前面有过同样的就合并
              {
                    if(a[j].s == a[i].s)
                     {
                            a[j].w += a[i].w;//合并
                            a[i].w = -1;//标记
                     }
                }
        }
    for(int i = 1; i <= n; i++)
       {
            if(a[i].w != -1)//合并到前面的就不考虑
             {
                    int p;
                   bool bo = false;
                 if (a[i].w % a[i].c > 0)//每放满一个格子，就算一个物件，占用一个空间，从而达到转01背包的作用
                      {
                            p = a[i].w / a[i].c + 1;
                         bo = 1;//标记，最后一个没放满
                      }
                    else
                     p = a[i].w / a[i].c;
                 for(int j = 1; j <= p; j++)//计算价值                                    {
                            if(bo == 1 && j == p)
                                {
                                    b[++t].v = a[i].v * (a[i].w % a[i].c);//如果最后一个没放满，要特判
                                    b[t].w = 1;//算占用一个空间
                             }
                            else
                             {
                                    b[++t].v = a[i].v * a[i].c;
                                  b[t].w = 1;
                              }
                        }
                }
        }
    for(int i = 1; i <= t; i++)
       for(int j = x; j >= b[i].w; j--)
          f[j] = max(f[j] , f[j - b[i].w] + b[i].v);//华丽的01背包模板
    cout << f[x];//输出
}