题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。 更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N 元钱就行”。

今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N 元。 于是，他把每件物品规定了一个重要度，分为5等：用整数1 ~5 表示，第5 等最重要。

他还从因特网上查到了每件物品的价格（都是整数元）。 他希望在不超过N 元（可以等于N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为v[j] ，重要度为w[j] ，共选中了k 件物品，编号依次为，，，，j1，j2，……，jk，则所求的总和为： v[j1]∗w[j1]+v[j2]∗w[j2]+…+v[jk]∗w[jk] 。（其中∗ 为乘号）

请你帮助金明设计一个满足要求的购物单。

输入格式

输入的第1 行，为两个正整数， N m （其中N<30000 ）表示总钱数，m<25 ）为希望购买物品的个数。）

从第2 行到第m+1 行，第j 行给出了编号为j−1 的物品的基本数据，每行有2 个非负整数 v p （其中v 表示该物品的价格(v<=10000) ，p表示该物品的重要度(1 ~5) )

输出格式

输出只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（）（<100000000）。

样例数据

input

10 5
8 2
4 5
3 5
4 3
2 2

output

39

题解

        物品有相应的价值和重要度，将不同物品的价值累加起来不超过总价值，且保证此时的重要度最大，每个物品只能用一次，所以是典型的01背包问题

        将总价值看作背包，将每个物品的价值放入背包，用每个物品更新不同总价值的最优值

一、阶段划分

        背包问题的阶段为不同的物品

二、状态表达

        用二维数组表示前i个物品，总价值为j时的最优值

        此时可以观察出，前i个物品的最优值只与前i-1个物品的最优值有关，且每个物品只能用一次

        所以可以将第二重循环，也就是背包的总价值倒着循环，利用第一层循环得到上一层更新的最优值

        所以只用开一维数组进行状态转移

三、初始状态

        因为总钱数不需要一定用完，也就是背包不一定要装满，所以赋初值为0

四、状态转移

        参考01背包模板

for(int i=1;i<=m;i++)
	for(int j=n;j>=0;j--)
		if(j>=pri[i]) f[j]=max(f[j],f[j-pri[i]]+pri[i]*imp[i]);

五、最终答案

         因为在状态转移更新最大值时，从n开始枚举，最大值赋给了f[j]，所以最大值最后赋给了f[n]

六、总结

        01背包中，为了节省空间，将两维化为一维，倒着枚举背包容量进行更新

七、核心DP代码实现

f[0]=0;
	for(int i=1;i<=m;i++)
		for(int j=n;j>=0;j--)
			if(j>=pri[i]) f[j]=max(f[j],f[j-pri[i]]+pri[i]*imp[i]);
	cout<<f[n];

八、本题代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int pri[30],imp[30];
int f[40000];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>pri[i]>>imp[i];
	}
	f[0]=0;
	for(int i=1;i<=m;i++)
		for(int j=n;j>=0;j--)
			if(j>=pri[i]) f[j]=max(f[j],f[j-pri[i]]+pri[i]*imp[i]);
	cout<<f[n];
}