P1964【mc生存】卖东西(洛谷)

题目描述：

lcy0x1去服务器的系统商店卖东西。

一个人的背包有21格。

一开始他的背包里有m件不同的物品（不能卖）。

他要卖n种物品，每种物品有ai件,价值bi,一格可以放ci个，

名字sti（0<sti的长度<100)

相同的物品可以放同一格(只要没放满）。

问他跑一次最多能卖多少钱。

输入格式：

第一行m,n(0<=m<=21,0<=n<=100)；

下面n行 ai,bi,ci,sti(0<=ai<=1344,0<=bi<=10000,0<ci<=64)；

输出格式：

最多卖的钱s(0<=s<=1000000)；

样例：

输入：

20 3
63 1 64 yinshifen
1 10 1 men
1 1 64 yinshifen

输出：

64

这个题比较乱感觉，但是能感受到考察的是dp背包问题，占的格数代替的就是物品的重量，但是这个题的数据好像不是很清楚，需要进行处理。

需要对物品的种类格数进行划分，格数足够一格了尽管是同一类物品也要看成两类，而如果数量加起来不到一格，就要合并成一个物品（体现最多卖的钱）。

所以我的思路就是用一个结构体对物品封装，先进行贪心处理，然后用01背包进行计算。

AC代码如下：

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

typedef struct object
{
   int piece,price,number,value;
   string name;
}ob;


int main()
{
    int m,n;
    int num[1000] = {0};
    ob o[1000];

    cin>>m>>n;
    m = 21 - m;
    int ans[1000][m+1];

    for(int i = 1;i <= n;i++)
    {
        cin>>o[i].piece>>o[i].price>>o[i].number>>o[i].name;
        for(int j = 1; j <= i;j++)
        {
            if(i != j && o[i].name == o[j].name)
            {
                if(o[i].piece + o[j].piece <= o[i].number)
                {
                    o[j].piece += o[i].piece;
                    n--;
                    i--;
                }
                else
                {
                    o[i].piece = o[i].piece - (o[j].number - o[j].piece);
                    o[j].piece = o[j].number;
                }
            }
        }
    }
    for(int i = 1;i <= n;i++)
    {
        o[i].value = o[i].piece * o[i].price;
    }
    for(int i = 1;i <= n;i++)
    {
        for(int j = m;j >= 1;j--)
        {
            ans[i][j] = max(ans[i-1][j],ans[i-1][j - 1]+o[i].value);
        }
    }
    cout<<ans[n][m]<<endl;
    return 0;
}