POJ—— 3624 Charm Bracelet（01背包）

红太狼 2021-09-26 11:36 174阅读 0赞

## 题目链接：[http://poj.org/problem?id=3624][http_poj.org_problem_id_3624] ##

## 题目： ##

## Charm Bracelet ##

Problem Description

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.

Input

\* 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*

Output

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

Sample Input

4 6
    1 4
    2 6
    3 12
    2 7

Sample Output

23

## 题目描述： ##

01背包问题。

## 代码： ##

#include<stdio.h> 
    #include<string.h>
    int f[15000];
    int e[3500];
    int w[3500];
    int a,b,c,i,j;
    int main()
    {
    	int t;
    	while(scanf("%d%d",&a,&b)!=EOF){
    		for(i = 0;i < a;i ++)
    			scanf("%d%d",&e[i],&w[i]);
    		memset(f,0,sizeof(f));
    		for(i = 0;i < a;i ++){
    			for(j = b;j >= e[i];j--){
    				f[j] = f[j] > f[j - e[i]] + w[i] ? f[j] : f[j - e[i]] + w[i];
    			}
    		}
    		printf("%d\n",f[b]);
    	}
    	return 0;
    }

[http_poj.org_problem_id_3624]: http://poj.org/problem?id=3624

发表评论取消回复

表情：

评论列表（有 0 条评论，174人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 3624 （01背包一维求解）

Charm Bracelet <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000

左手的ㄟ右手/ 2024年02月17日 19:31/ 0 赞/ 6 阅读

相关 Charm Bracelet（经典例题0-1背包）

https://ac.nowcoder.com/acm/problem/25029 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVp

Love The Way You Lie/ 2022年11月19日 04:27/ 0 赞/ 114 阅读

相关 Charm Bracelet

题目：描述 Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of cour

淩亂°似流年/ 2022年07月14日 13:58/ 0 赞/ 13 阅读

相关 01背包问题 poj 3624

理解01背包问题，首先要从二维数组的开始。二维数组的理解之后，优化成为一维，就是轻而易举的事了。 01背包动态规划的转移公式：当考虑第i件物品的时候，背包能装得下的话

落日映苍穹つ/ 2022年06月13日 10:50/ 0 赞/ 91 阅读

相关 poj 3624 - Charm Bracelet

1. 地址 [http://poj.org/problem?id=3624][http_poj.org_problem_id_3624] 2. 定位动态规

╰半夏微凉°/ 2022年06月08日 07:21/ 0 赞/ 72 阅读

相关 POJ 3624 Charm Bracelet【01背包】

Charm Bracelet 题目链接：[https://vjudge.net/contest/209202\problem/L][https_vjudge.net_c

末蓝、/ 2022年06月01日 10:14/ 0 赞/ 75 阅读

相关 poj3624 Charm Bracelet

Charm Bracelet Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 44500 Acc

爱被打了一巴掌/ 2022年05月26日 23:08/ 0 赞/ 79 阅读

相关 Charm Bracelet POJ - 3624 (利用滚动数组解决01背包)

Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd

雨点打透心脏的1/2处/ 2022年02月24日 14:54/ 0 赞/ 193 阅读

相关 POJ 3624 Charm Bracelet(01背包模板题)

[题目链接][Link 1] <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000

Dear 丶/ 2021年12月03日 14:51/ 0 赞/ 186 阅读

相关 POJ—— 3624 Charm Bracelet（01背包）

题目链接：[http://poj.org/problem?id=3624][http_poj.org_problem_id_3624] 题目： Charm

红太狼/ 2021年09月26日 11:36/ 0 赞/ 175 阅读