POJ 3624 Charm Bracelet【01背包】
2024-08-31 08:41:41
解题思路:直接套公式就能做的01背包,
for(i=1;i<=n;i++)
{
for(v=w[i];v<=m;v++)
f[i,v]=max(f[i,v],f[i-1,v-w[i]]+d[i]);//只想明白了可以用一维数组来存放包的价值,因为我们需要的只是包的最大价值,不用记录是第几个包的时候,有最大价值,然后v从w[i]到包的总容量循环不明白。
}
for(i=1;i<=n;i++)
{
for(v=m;v>=c[i];v--) //即最开始给定包的总容量(此时包是空的),循环跳出条件是预留出现在正在放入的这个包的体积(这样你可以选择放入或者不放入),然后放下一个包的时候,之前包的总价值也被记录下来了。
f[v]=max(f[v],f[v-w[i]]+d[i]);
}
#include<stdio.h>
#include<string.h>
int f[15000],w[3500],d[3500];
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int main()
{
int n,m;
int i,v;
while(scanf("%d %d",&n,&m)!=EOF)
{
memset(f,0,sizeof(f));
for(i=1;i<=n;i++)
scanf("%d %d",&w[i],&d[i]);
for(i=1;i<=n;i++)
{
for(v=m;v>=w[i];v--)
{
f[v]=max(f[v],f[v-w[i]]+d[i]);
}
}
printf("%d\n",f[m]);
}
}
最新文章
- 基于UDP的网络编程
- jstl中格式化时间戳
- sublime text3下BracketHighlighter的配置方法
- 五种开源协议(GPL,LGPL,BSD,MIT,Apache)
- rhino(犀牛) --- color control
- [转载]《C++0x漫谈》系列之:多线程内存模型
- rac各节点实例需设置为相同的一些参数
- ZOJ-3933-Team Formation【二分图最佳匹配】【KM】
- 一次php涉及跨域功能的麻烦及解决方案
- CentOS6.x机器安装Python2.7.x
- mysql语法、特殊符号及正则表达式的使用
- 【原创】架构师必备,带你弄清混乱的JAVA日志体系!
- app微信支付-java服务端接口 支付-查询-退款
- PHP——运行shell命令|脚本
- Hadoop的启动和停止说明
- Inno Setup 系列之安装、卸载前检测进程运行情况并关闭相应进程
- 清明 DAY 1
- python3自学第二天,模块,三元运算
- boost并发编程boost::atomic
- wps插件开发中com组件权限