NYOJ,106,背包问题

2024-06-12 07:18
文章标签 问题 背包 nyoj 106

本文主要是介绍NYOJ,106,背包问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

背包问题

时间限制:3000 ms  |  内存限制:65535 KB

难度:3

描述

现在有很多物品(它们是可以分割的),我们知道它们每个物品的单位重量的价值v和重量w(1<=v,w<=10);如果给你一个背包它能容纳的重量为m(10<=m<=20),你所要做的就是把物品装到背包里,使背包里的物品的价值总和最大。

输入

第一行输入一个正整数n(1<=n<=5),表示有n组测试数据;
随后有n测试数据,每组测试数据的第一行有两个正整数s,m(1<=s<=10);s表示有s个物品。接下来的s行每行有两个正整数v,w。

输出

输出每组测试数据中背包内的物品的价值和,每次输出占一行。

样例输入

1

3 15

5 10

2 8

3 9

样例输出

65

 

 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct
{
int v;
int w;
}pa;
pa a[30];
int cmp(const void *a,const void *b)
{
pa *a1=(pa *)a;
pa *b1=(pa *)b;
return b1->v-a1->v;
}
int main()
{
int n,s,m,i,j,ans;
scanf("%d",&n);
while (n--)
{
scanf("%d%d",&s,&m);
for (i=1;i<=s;i++)
scanf("%d%d",&a[i].v,&a[i].w);
qsort(a+1,s,sizeof(a[0]),cmp);
ans=0;
for (i=1;i<=s;i++)
for (j=1;j<=a[i].w;j++)
if (m-1>=0)
{
ans+=a[i].v;
m--;
}
printf("%d\n",ans);
}
return 0;
}        


坑啊,我还以为是01背包呢,竟然是伪背包问题,单位重量的价值?物品还可以分割?

 

 

 

 

 

这篇关于NYOJ,106,背包问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1053544

相关文章

详谈redis跟数据库的数据同步问题

《详谈redis跟数据库的数据同步问题》文章讨论了在Redis和数据库数据一致性问题上的解决方案,主要比较了先更新Redis缓存再更新数据库和先更新数据库再更新Redis缓存两种方案,文章指出,删除R... 目录一、Redis 数据库数据一致性的解决方案1.1、更新Redis缓存、删除Redis缓存的区别二

oracle数据库索引失效的问题及解决

《oracle数据库索引失效的问题及解决》本文总结了在Oracle数据库中索引失效的一些常见场景,包括使用isnull、isnotnull、!=、、、函数处理、like前置%查询以及范围索引和等值索引... 目录oracle数据库索引失效问题场景环境索引失效情况及验证结论一结论二结论三结论四结论五总结ora

element-ui下拉输入框+resetFields无法回显的问题解决

《element-ui下拉输入框+resetFields无法回显的问题解决》本文主要介绍了在使用ElementUI的下拉输入框时,点击重置按钮后输入框无法回显数据的问题,具有一定的参考价值,感兴趣的... 目录描述原因问题重现解决方案方法一方法二总结描述第一次进入页面,不做任何操作,点击重置按钮,再进行下

解决mybatis-plus-boot-starter与mybatis-spring-boot-starter的错误问题

《解决mybatis-plus-boot-starter与mybatis-spring-boot-starter的错误问题》本文主要讲述了在使用MyBatis和MyBatis-Plus时遇到的绑定异常... 目录myBATis-plus-boot-starpythonter与mybatis-spring-b

mysql主从及遇到的问题解决

《mysql主从及遇到的问题解决》本文详细介绍了如何使用Docker配置MySQL主从复制,首先创建了两个文件夹并分别配置了`my.cnf`文件,通过执行脚本启动容器并配置好主从关系,文中还提到了一些... 目录mysql主从及遇到问题解决遇到的问题说明总结mysql主从及遇到问题解决1.基于mysql

如何测试计算机的内存是否存在问题? 判断电脑内存故障的多种方法

《如何测试计算机的内存是否存在问题?判断电脑内存故障的多种方法》内存是电脑中非常重要的组件之一,如果内存出现故障,可能会导致电脑出现各种问题,如蓝屏、死机、程序崩溃等,如何判断内存是否出现故障呢?下... 如果你的电脑是崩溃、冻结还是不稳定,那么它的内存可能有问题。要进行检查,你可以使用Windows 11

如何安装HWE内核? Ubuntu安装hwe内核解决硬件太新的问题

《如何安装HWE内核?Ubuntu安装hwe内核解决硬件太新的问题》今天的主角就是hwe内核(hardwareenablementkernel),一般安装的Ubuntu都是初始内核,不能很好地支... 对于追求系统稳定性,又想充分利用最新硬件特性的 Ubuntu 用户来说,HWEXBQgUbdlna(Har

MAVEN3.9.x中301问题及解决方法

《MAVEN3.9.x中301问题及解决方法》本文主要介绍了使用MAVEN3.9.x中301问题及解决方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录01、背景02、现象03、分析原因04、解决方案及验证05、结语本文主要是针对“构建加速”需求交

Nginx、Tomcat等项目部署问题以及解决流程

《Nginx、Tomcat等项目部署问题以及解决流程》本文总结了项目部署中常见的four类问题及其解决方法:Nginx未按预期显示结果、端口未开启、日志分析的重要性以及开发环境与生产环境运行结果不一致... 目录前言1. Nginx部署后未按预期显示结果1.1 查看Nginx的启动情况1.2 解决启动失败的

CentOS系统使用yum命令报错问题及解决

《CentOS系统使用yum命令报错问题及解决》文章主要讲述了在CentOS系统中使用yum命令时遇到的错误,并提供了个人解决方法,希望对大家有所帮助,并鼓励大家支持脚本之家... 目录Centos系统使用yum命令报错找到文件替换源文件为总结CentOS系统使用yum命令报错http://www.cppc