首页 > 代码库 > 开心的小明
开心的小明
- 输入
- 第一行输入一个整数N(0<N<=101)表示测试数据组数
每组测试数据输入的第1 行，为两个正整数，用一个空格隔开：
N m
（其中N（<30000）表示总钱数，m(<25)为希望购买物品的个数。）
从第2 行到第m+1 行，第j 行给出了编号为j-1
的物品的基本数据，每行有2 个非负整数
v p
（其中v 表示该物品的价格（v≤10000），p 表示该物品的重要度（1~5）） - 输出
- 每组测试数据输出只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的
最大值（<100000000） - 样例输入
1 1000 5 800 2 400 5 300 5 400 3 200 2
- 样例输出
3900
解题思路：
此题用到动态规划，求取全局最优解。
首先要自定义函数求两个数的最大值，得到每一步的最优解。
定义数组时应当将数组稍稍定大一点，以免输出超限。
应用memset（）将定义的数组初始化。
程序代码：
#include<stdio.h> #include<string.h> #define max(a,b) a>b?a:b int n,m; int v[10005]; int p[6]; int t[30005]; int main() { int i,j; int s; scanf("%d",&s); while(s--) { scanf("%d%d",&n,&m); memset(t,0,sizeof(t)); memset(p,0,sizeof(p)); memset(v,0,sizeof(v)); for(i=1;i<=m;i++) { scanf("%d%d",&v[i],&p[i]); //printf("%d %d\n",v[i],p[i]); for(j=n;j>=v[i];j--) { t[j]=max(t[j],t[j-v[i]]+p[i]*v[i]); } } printf("%d\n",t[n]); } return 0; }
开心的小明
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。