https://www.oj.swust.edu.cn/problem/show/1194

1194: 买月饼

Time Limit: 1000 MS Memory Limit: 65536 KB
 

Description

中秋节马上就要到了，小Y计划给基友买月饼。由于经济压力，小Y计算最多只用M元钱买月饼。超市有N种月饼，每种都有单价。由于有些月饼比较抢手，剩下的个数有限，有的月饼有无限多个。小Y的基友对于每种月饼都有不一样的喜爱程度。小Y为了让基友尽可能的高兴，他想用计算之内的钱购买的月饼使得基友的喜爱程度最高。（每个月饼都有一个喜爱度。基友的喜爱程度是小Y购买到月饼的喜爱度的总和。）

 

Input

多组输入。 首先输入一个M，N。表示小Y计划用的钱和超市的月饼种类。（0 < M <= 10000,0 < N <= 5000） 接下来n行，每行3个整likei,wi,numi,分别表示第i种月饼的喜爱度,单价和个数。（0 <= likei <= 10000,100 <= wi <= 10000,土豪月饼，单价比较高，numi=-1表示月饼有无限多个，否则0 <= numi <= 10000，保证个数有限的种类 <= 10）

Output

输出一行整数表示最大的喜爱度。

100 1

1 100 -1

500 1

1 101 1

1

1

三种背包 ，如果数目为1，0 1背包，数目为-1，完全背包，其他就是多重背包。

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
int max(int x,int y)
{
    return x>y?x:y;
 
}
int main()
{
    int money;
    int type;
int like[50005];
    int danjia[50005];
    int number[50005];
 int i;
 
    int j;
    int dp[50005];
   while(scanf("%d%d",&money,&type)!=EOF)
   {
 
 memset(dp,0,sizeof(dp));
   for(i=0;i<type;i++)
    {
        scanf("%d%d%d",&like[i],&danjia[i],&number[i]);
    }
    for(i=0;i<type;i++)
    {
        if(number[i]==1)
        {
            for(j=money;j>=danjia[i];j--)
            {
                dp[j]=max(dp[j],dp[j-danjia[i]]+like[i]);
            }
        }
        else if(number[i]==-1)
        {
            for(j=danjia[i];j<=money;j++)
            {
                dp[j]=max(dp[j],dp[j-danjia[i]]+like[i]);
            }
        }
         else
         {
             for(int k=0;k<number[i];k++)
             for(j=money;j>=danjia[i];j--)
            {
                dp[j]=max(dp[j],dp[j-danjia[i]]+like[i]);
            }
         }
    }
    printf("%d\n",dp[money]);
   }
    return 0;
}