本文主要是介绍Power oj 1194 买月饼 三种背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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
输出一行整数表示最大的喜爱度。
- Sample Input
- Raw
100 1
1 100 -1
500 1
1 101 1
- Sample Output
- Raw
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;
}
这篇关于Power oj 1194 买月饼 三种背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
