博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
洛谷——2871[USACO07DEC]手链Charm Bracelet——01背包
阅读量:5821 次
发布时间:2019-06-18

本文共 1488 字,大约阅读时间需要 4 分钟。

题目描述

Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight Wi (1 ≤ Wi ≤ 400), a 'desirability' factor Di (1 ≤ Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).

Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.

有N件物品和一个容量为V的背包。第i件物品的重量是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量,且价值总和最大。

输入输出格式

输入格式:

 

  • Line 1: Two space-separated integers: N and M

  • Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di

 

输出格式:

 

  • Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints

 

输入输出样例

输入样例#1:
4 61 42 63 122 7
输出样例#1:
23 代码
#include
#include
#include
#include
#include
using namespace std;int n,v,c[3403],d[3403],f[1000000];int main(){ scanf("%d%d",&n,&v); for(int i=1;i<=n;i++) { scanf("%d%d",&d[i],&c[i]); } for(int i=1;i<=n;i++) for(int m=v;m>=d[i];m--) f[m]=max(f[m],f[m-d[i]]+c[i]); printf("%d",f[v]); return 0;}

 

 

转载于:https://www.cnblogs.com/z360/p/6719136.html

你可能感兴趣的文章
HCNA——RIP的路由汇总
查看>>
zabbix监控php状态(四)
查看>>
实战Django:小型CMS Part2
查看>>
原创]windows server 2012 AD架构试验系列 – 16更改DC计算机名
查看>>
统治世界的十大算法
查看>>
linux svn安装和配置
查看>>
SSH中调用另一action的方法(chain,redirect)
查看>>
数据库基础
查看>>
表格排序
查看>>
关于Android四大组件的学习总结
查看>>
java只能的round,ceil,floor方法的使用
查看>>
由于无法创建应用程序域,因此未能执行请求。错误: 0x80070002 系统找不到指定的文件...
查看>>
新开的博客,为自己祝贺一下
查看>>
【CQOI2011】放棋子
查看>>
采用JXL包进行EXCEL数据写入操作
查看>>
一周总结
查看>>
将txt文件转化为json进行操作
查看>>
线性表4 - 数据结构和算法09
查看>>
C语言数据类型char
查看>>
Online Patching--EBS R12.2最大的改进
查看>>