NYOJ 49-开心的小明(经典01背包)--内附背包九讲2.0PDF_背包问题九讲2.0 下载-程序员宅基地

开心的小明

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 4

描述

小明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N 元钱就行”。今天一早小明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N 元。于是，他把每件物品规定了一个重要度，分为5 等：用整数1~5 表示，第5 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N 元（可以等于N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j 件物品的价格为v[j]，重要度为w[j]，共选中了k 件物品，编号依次为j1...jk，则所求的总和为：v[j1]*w[j1]+..+v[jk]*w[jk]请你帮助金明设计一个满足要求的购物单.

输入

第一行输入一个整数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）

样例输入

样例输出

//01背包模板题，直接套01背包模板

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define maxn 30005
using namespace std;

int dp[maxn];
int v[27];
int p[27];

int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		int n, m;
		scanf("%d%d", &n, &m);
		for(int i=0; i<m; i++)
			scanf("%d%d", &v[i], &p[i]);
		memset(dp, 0, sizeof(dp));

		//0-1背包模板
		for(int i=0; i<m; i++)
			for(int j=n; j>=v[i]; j--)
			{
				dp[j] = max(dp[j], dp[j-v[i]] + p[i]*v[i]);
			}
		printf("%d\n", dp[n]);
	}
	return 0;
}

本文链接：https://blog.csdn.net/qq_31281327/article/details/75298971

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

C语言操作链表详解_c语言链表使用-程序员宅基地

文章浏览阅读2.3k次，点赞7次，收藏38次。C语言操作链表详解链表的概念链表的操作将数据抽象成结构体创建和初始化链表输出链表中存储的数据查找链表中指定位置中存储的数据在链表中插入数据删除指定位置的数据修改制定位置的数据逆序输出链表存储的数据执行结果在我们学习C语言的前期，每当我们要进行大量数据的读写时，我们都会使用顺序表，也就数组，它的优点很明显，增删读写操作很简单，易于上手。但当我们对数据的存储理解更加深刻时，我们便会逐渐意识到顺序表也不是万能的，它也有它的缺点：顺序表在内存中的存储时，占用一大块连续的空间，但我们实际在使用时，可能并没有那么大的_c语言链表使用

如何 make menuconfig 和 make xconfig_linux make xconfig-程序员宅基地

文章浏览阅读1.3k次。在ubuntu系统中，要编译内核，还需要安装一系列相应的工具才行。这篇文章，正是针对这一过程的一次记录，目标是可以通过 make menuconfig 或 make xconfig 配置内核参数--------------------------------------------------------------参考apt用法参考《 UbuntuHelp:AptGet/How_linux make xconfig

从0到1学SpringCloud——13 gateway RouteLocator配置路由规则-程序员宅基地

文章浏览阅读1.5k次。上一篇介绍了通过数据库配置断言信息来实现动态路由的方式，今天介绍通过RouteLocator如何配置路由信息_gateway routelocator

ffmpeg--学习笔记2-编译、学习_--enable-indev=v4l2-程序员宅基地

文章浏览阅读1k次。参考博客：http://bbs.eeworld.com.cn/thread-505971-1-1.html Windows 版本的编译好的文件下载地址：http://ffmpeg.zeranoe.com/builds/ Linux版本Git地址：git://source.ffmpeg.org/ffmpeg.git 说来尴尬，我是在Windows电脑上面直接安装编译好的文件的所以导致很多的编译细节不_--enable-indev=v4l2

SpringCloud之搭建eureka注册中心_springcloud 设置注册信息 version-程序员宅基地

文章浏览阅读1.2k次，点赞2次，收藏2次。<?xml version="1.0" encoding="UTF-8"?><project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://mave..._springcloud 设置注册信息 version

atoi()函数(char类型字符串转int)_temp1[i] = atoi(buffer);-程序员宅基地

文章浏览阅读2.9k次。int atoi(const char *str)描述C 库函数 int atoi(const char *str) 把参数 str 所指向的字符串转换为一个整数（类型为 int 型）。参数str -- 要转换为整数的字符串。返回值成功时，该函数返回转换后的整数作为int值。如果转换后的值超出a的可表示值范围int，则会导致未定义的行为。若无法进行转换，则返回 0。..._temp1[i] = atoi(buffer);

随便推点

C 语言中 static 和 extern 全局变量的使用_如果全局区定义了一个static变量,在整个项目任何地方是否都可以访问?-程序员宅基地

文章浏览阅读1.7k次，点赞7次，收藏5次。一、基础知识1. 定义和声明定义：定义变量用于为变量分配存储空间，还为变量指定初始值，在一个程序中，变量有且仅有一个定义。声明：声明用于向程序表明变量的类型和名字。2. 全局变量默认是 extern的3. 在一个程序中，外部变量仅有一个定义。C语言代码是以文件为单位来组织的在一个源程序的所有源文件（.c，.cpp）中，一个外部变量（注意不是局部变量）或者函数只能在一个源程序中定..._如果全局区定义了一个static变量,在整个项目任何地方是否都可以访问?