NKOJ 3793 礼物和糖果（背包dp）

发表于 |
字数统计: 395字 | 阅读时长 ≈ 2min

P3793礼物和糖果

问题描述

何老板要给大家买节日礼物，他有M元钱，学校小卖部有N种礼品，因为店长和何老板是熟人，所以若第i种礼品买x(x>0)件的话，店长会给何老板Ai*x+Bi颗糖果。
因为何老板非常喜欢吃糖，所以他希望获得的糖果越多越好。现给出每种礼品的单价Wi、Ai值与Bi值，问何老板最多能得到多少颗糖果？

输入格式

第一行，两个空格间隔的整数M和N
接下来N行，每行三个整数Wi, Ai 和 Bi，描述一种礼物的情况。

输出格式

一行，一个整数，表示何老板能得到的最大糖果数

样例输入

100 2
10 2 1
20 1 1

样例输出

21

提示

1 ≤ M ≤ 2000
1 ≤ N ≤ 1000
0 ≤ Ai, Bi ≤ 2000
1 ≤ Wi ≤ 2000

将一个物品拆成两个物品，一个物品价格为$A[i]+B[i]$，只能买一个。
另一个物品价格为$A[i]$，可以买无限个。
然后背包dp即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define N 2222
using namespace std;
int m,n,W[N],A[N],B[N],F[N];
int main()
{
	int i,j,k;
	scanf("%d%d",&m,&n);
	for(i=1;i<=n;i++)scanf("%d%d%d",&W[i],&A[i],&B[i]);
	for(i=1;i<=n;i++)
	{
		for(j=m;j>=W[i];j--)F[j]=max(F[j],F[j-W[i]]+A[i]+B[i]);
		for(j=W[i];j<=m;j++)F[j]=max(F[j],F[j-W[i]]+A[i]);
	}
	cout<<F[m];
}