POJ-2184 Cow Exhibition---01背包变形(负数偏移)
2024-08-25 12:57:52
题目链接:
https://vjudge.net/problem/POJ-2184
题目大意:
给出num(num<=100)头奶牛的S和F值(-1000<=S,F<=1000),要求在这几头奶牛中选出若干头,使得在其总S值TS和总F值TF均不为负的前提下,求最大的TS+TF值
思路:
可以把S当体积,F当价值做01背包。但是注意是S可为负,所以整体加100000,然后要注意DP顺序,S为负是要顺序,为正时逆序。
还有就是注意DP时的范围,凡是可能影响的都要包括。
//#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = ;
const int maxm = 2e5+;
const int INF = 0x3f3f3f3f;
int v[maxn], w[maxn];
int dp[maxm];
int T, n;
double m;
int main()
{
int k = ;//整体偏移k位,dp[k]就是标准的dp[0]
while(cin >> n)
{
memset(dp, -INF, sizeof(dp));
dp[k] = ;//注意初始化
int x, y;
for(int i = ; i < n; i++)
{
cin >> x >> y; //这里不能写if(x+y<0)continue;这是错误的贪心,一开始因为这个地方一直WA,因为有些x+y<0加入是由于x>0 y<0,x的加入使得x和其他的最优解非负
if(x <= && y <= )continue;//可以直接由贪心排除 if(x < )//x小于0,dp转移方向从前往后,因为每一步dp[i]需要dp[i-x]更新,由于是负数i-x>i
{
for(int i = ; i <= * k + x; i++)
if(dp[i - x] > -INF)//这里不能省略,如果dp[i - x]为-INF,那么就不可以更新前面的值
dp[i] = max(dp[i], dp[i - x] + y);
} else //x大于0,dp转移方向从后往前,就是01背包
{
for(int i = * k; i >= x; i--)
if(dp[i - x] > -INF)
dp[i] = max(dp[i], dp[i - x] + y);
}
}
int ans = ;
for(int i = k; i <= * k; i++)//从k开始,结果减去k
if(dp[i] >= )//此处必须大于0,因为dp[i]为TF的值,题目要求TF非负
ans = max(ans, dp[i] + i - k);
cout<<ans<<endl;
}
return ;
}
最新文章
- Maven打包 报 Unable to locate the Javac Compiler in: C:\Program Files\Java\jre1.8.0_73\..\lib\tools.jar
- etl结合java的例子
- JS 删除对象属性
- svn学习笔记(2)操作----还原,重命名,冲突处理,权限配置等
- LeetCode——Gas Station
- java批量插入数据进数据库中
- sampleGradient(sampler,uv,dds,ddy)
- Linux查看目录挂载点
- 你真的了解 console 吗
- 两台linux机器文件传输之scp
- 14.3.5.1 An InnoDB Deadlock Example
- 使用composer更新thinkphp5或则yii2的版本
- 前端技术之_CSS详解第六天--完结
- STM32f030f4p6 内部flash 打包读写
- Python从入门到放弃Day01
- Python内置函数之classmetho staticmethod
- 51nod 省选联测 R2
- 《linux就该这么学》第四节课笔记,三章和四章开始!
- GetSystemInfo 和 GlobalMemoryStatus获取系统信息,内存信息
- JDK动态代理源码分析
热门文章
- NGUI_Label
- windows下安装Virtualenvwrapper
- ASP.NET MVC编程——验证、授权与安全
- eventProxyAPI(转)
- 【MySQL】MySQL零碎积累
- “Swift Language Version” (SWIFT_VERSION) build setting must be set to a supported value for targets which use Swift
- 2017-2018-1 20155215 第九周 加分项 PWD命令的实现
- 201621123062《java程序设计》第11周作业总结
- GPUImage实战问题解决
- 【学习笔记】windows安装jhipster踏坑记录