搜索
房产
装修
汽车
婚嫁
健康
理财
旅游
美食
跳蚤
二手房
租房
招聘
二手车
教育
茶座
我要买房
买东西
装修家居
交友
职场
生活
网购
亲子
情感
龙城车友
找美食
谈婚论嫁
美女
兴趣
八卦
宠物
手机

【做题笔记】P2871 [USACO07DEC]手链Charm Bracelet

[复制链接]
查看: 106|回复: 0

1万

主题

1万

帖子

4万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
45261
发表于 2020-2-14 22:37 | 显示全部楼层 |阅读模式
就是 01 背包。大意:给您 \(T\) 个空间巨细的限制,有 \(M\) 个物品,第 \(i\) 件物品的重量为 \(c_i\) ,价格为 \(w_i\) 。要求挑选一些物品,使得总空间不横跨 \(T\) ,且总价格最大。
考虑设 \(f_{i,j}\) 为 \(1\) ~ \(i\) 件物品,背包容量为 \(j\) 时的最大价格,那末假如不选第 \(i\) 件物品,则为 \(f_{i-1,j}\) 的子题目(背包内只要 \(i-1\) 个物品);若选,则为 \(f_{i-1,j-w_i}+v_i\) 的子题目。
[code]#include #include #include using namespace std;int f[1001][1001],T,M,w[100001],v[100001];int main(){    cin>>T>>M;    for(int i=1;i>w>>v;    for(int i=1;iv;    for(int i=1;i=w;--j)            f[j]=max(f[j],f[j-w]+v);    cout
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Copyright © 2006-2014 全椒百姓网-全椒知名**,发布及时新鲜的全椒新闻资讯 生活信息 版权所有 法律顾问:高律师 客服电话:0791-88289918
技术支持:迪恩网络科技公司  Powered by Discuz! X3.2
快速回复 返回顶部 返回列表