此题是二维的背包问题,不会的请先看《背包九讲》(虽然我也没看明白,但还是值得一看),这里再说一句,学算法最好是拿例题来实践,而实践最好是要有大量测试数据,
能过测试数据能够很明确地找出自己的错误来,并且能使人对算法的处理过程有个很明朗的了解。希望各大OJ网站能够高抬贵手,像USCAOG 一样将后台测试数据展现出来,帮助更多在错误中死去活来的 acmer 们走出迷途!
/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2011 panyanyany All rights reserved.
URL : http://acm.hdu.edu.cn/showproblem.php?pid=2159
Name : 2159 FATE
Date : Saturday, August, 06, 2011
Time Stage :6 hours around
Result:
4348182 2011-08-06 16:27:14 Accepted 2159
15MS 228K 1399 B
C++ pyy
Test Data:
Review:
//----------------------------------------------------------------------------*/
#include <stdio.h>
#include <string.h>
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))
#define MAXSIZE 101
int need, remain, kind, kill ;
int val[MAXSIZE], cost[MAXSIZE], dp[MAXSIZE][MAXSIZE] ;
int twoDimension ()
{
int i, j, k ;
memset (dp, 0, sizeof (dp)) ;
for (i = 1 ; i <= kind ; ++i)
{
for (j = 1 ; j <= kill ; ++j)
{
for (k = cost[i] ; k <= remain ; ++k)
{
dp[j][k] = max (dp[j][k], dp[j-1][k-cost[i]] + val[i]) ;
}
}
}
// 一开始在外面加了层1.....kill 的循环,想找到杀怪数最少并且忍耐度消耗最少
// 时最先到达need 的值,结果一直错。
// 因为有可能杀一只怪,消耗的忍耐度比杀五只怪还大
for (i = 1 ; i <= remain ; ++i)
{
// printf ("%d,%d ", dp[kill][i], i) ;
if (dp[kill][i] >= need)
break ;
}
// puts ("") ;
if (i > remain)
return -1 ;
return remain - i ;
}
int main ()
{
int i, j ;
while (scanf ("%d%d%d%d", &need, &remain, &kind, &kill) != EOF)
{
for (i = 1 ; i <= kind ; ++i)
{
scanf ("%d%d", &val[i], &cost[i]) ;
}
printf ("%d\n", twoDimension ()) ;
}
return 0 ;
}
分享到:
相关推荐
HDC1080 IIC通讯例程,注释清晰,可正常使用
本文是基于STM32F407开发的,为了便于理解和大家移植,使用模拟IIC与HDC1080进行通信,内容含逻辑分析仪的IIC波形图。
驱动传感器HDC1080(TI公司旗下的产品,用于检测温湿度的传感器)。
HDC1080 是一款具有集成温度传感器的数字湿度传感器,其能够以超低功耗提供出色的测量精度。HDC1080 支持较宽的工作电源电压范围,并且相比竞争解决方案,该器件可为各类常见应用提供低成本和低功耗 优势。本程序能...
HDC2010温湿度传感器的驱动,有不对的地方望大佬指点
内含超好用IIC接口代码!超级好用的IIC代码!炒鸡好用的IIC代码!IIC接口修改宏定义即可,HDC2010的各个功能方法已经全部实现,亲测好使已经用于项目。具体采集代码附件里面HDC2010 Arduino_Library_1.0。
HDC1080 是一款具有集成温度传感器的数字湿度传感器,其能够以超低功耗提供出色的测量精度。HDC1080 支持较宽的工作电源电压范围,并且相比竞争解决方案,该器件可为各类常见应用提供低成本和低功耗 优势。本程序能...
气体传感器,CCS811 HDC1080 二氧化碳 CO2 传感器模块 温湿度 VOCs 空气质量,含有测程序,数据手册等等资源
hdc_std是OpenHarmony提供的用于调试的命令行工具,通过该工具可以在Windows/Linux等系统上与开发机或者模拟器进行交互。 目前,OpenHarmony不再提供编译好的hdc_std,需要开发者拉取该工具的源码自行编译。 本仓库...
HDC1080温湿度传感器驱动程序 HDC1080-With-STM32 In this projects I will use STM32F103C8 read temperature and humidity from HDC1080 via I2C
更新内容:增加小数点输出,文件为HDC1080温湿度传感器的C语言STM32驱动程序,已经调试成功!!!I2C接口,可以正常配置寄存器,读取温度值,内含非常详细的注释。
索尼HDC-2580系统摄像机的诞生,为高清演播室/转播车的现场节目制作提供了一个强大的全线解决方案。HDC-2580系统组成包括:索尼的旗舰型号摄像机头HDC-2580
TI的HDC1050低功耗温湿度传感器芯片手册英文版
获得CDC * CDC* pDC pDC=GetDC();//原型CDC* CWnd::GetDC() 获得hdc HDC hDC; 1,hDC=GetDC(pCpp->hWnd); 2,pDC->m_hDC;
本文件为TI温湿度传感器HDC1080的C语言驱动程序,可以正常配置寄存器,读取温度值,I2C接口,内含注释。
基于STM32F207的HDC1080的模拟I2C驱动程序,可以实现HDC1080的温湿度读取,注释清楚,完美运行。
hdc1080数据手册 ,是一款高精度的温湿度传感器,是TI公司出品的
Digital Bcakground HDC calibration
主要描述了HDC与CDC两者间的相互转换的方法。
HDC1000 手册 很细的说明