饭卡---hdu2546(01背包)
2024-10-20 18:59:34
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2546
这是一个变形的01背包问题,首先如果金额小于5元,剩余金额不变,为已有金额。如果大于等于5元
我们先用5元买最贵的菜。然后用剩下的钱买其他的菜这时就是一个典型的01背包问题了;
求出最大的花费,然后用总金额减去最大的花费即为剩余金额。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std; #define INF 0xfffffff
#define N 1005
int a[N], dp[N][N]; int main()
{
int n, m;
while(scanf("%d", &n), n)
{
for(int i=; i<=n; i++)
scanf("%d", &a[i]);
scanf("%d", &m);
if(m<)
{
printf("%d\n", m);
continue;
}
m-=;
sort(a+, a+n+);
for(int i=; i<n; i++)
{
for(int j=; j<=m; j++)
{
dp[i][j] = dp[i-][j];///千万不能忘的;
if(j>=a[i])
dp[i][j] = max(dp[i-][j], dp[i-][j-a[i]]+a[i]);
}
}
printf("%d\n", m+-dp[n-][m]-a[n]);
}
return ;
}
二维数组
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std; #define INF 0xfffffff
#define N 1005
int a[N], dp[N]; int main()
{
int n, m;
while(scanf("%d", &n), n)
{
memset(a, , sizeof(a));
memset(dp, , sizeof(dp));
for(int i=; i<=n; i++)
scanf("%d", &a[i]);
scanf("%d", &m);
if(m<)
{
printf("%d\n", m);
continue;
}
m-=;
sort(a+, a+n+);
for(int i=; i<n; i++)
{
for(int j=m; j>=a[i]; j--)
{
dp[j] = max(dp[j], dp[j-a[i]]+a[i]);
}
}
printf("%d\n", m+-dp[m]-a[n]);
}
return ;
}
一维数组
最新文章
- oracle的sqlnet.ora,tnsnames.ora,listener.ora三个配置文件
- KBMMW 中 IOS IPv6 的解决
- Java 名词
- C++智能指针简单剖析
- PHP include语句和require语句
- Android AlertDialog
- HW6.20
- OpenCV快速遍历矩阵元素方法
- selenium1.0和selenium2.0页面等待处理详解
- 关于 mod_python
- SpringMVC入门1
- qq邮箱是怎么做到同一个浏览器让多个不用用户同时打开的? --session的控制
- python3语法小记(二)列表 和 元组
- poj 2485 (kruskal算法)
- 读书笔记-你不知道的JS上-this
- Java数据库连接池详解
- redis多实例和高可用
- (8)Microsoft office Word 2013版本操作入门_制作传单海报
- Elasticsearch 关键字:索引,类型,字段,索引状态,mapping,文档
- 工具篇-Mac上搭建本地svn服务器以及使用Cornerstone进行本地版本控制