POJ - 3624Charm Bracelet（01背包）

Charm Bracelet

Descriptions:

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 MLines 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

题目链接： https://vjudge.net/problem/POJ-3624

题解：

先简单翻译一下（可能都被英文整懵了，就说一下大概意思，中间部分物品简化了，不影响做题） 已知n个糖果的重量和价值. 我们有一个口袋, 最多可以装m重量的糖果. 问口袋最多能放多少价值的糖果进去? 输入： 第1行：两个以空格分隔的整数：n和m 第2行：N 1：第i 1行描述具有两个以空格分隔的整数的魅力i：Wi和Di ，即重量和价值 输出：第1行：单个整数即在重量限制的情况下，可以实现的最大可取性 开始题解了哈 标准的01背包问题，非常经典，没有任何坑，用数组记录每一件物品的重量w[i]，价值v[i]，背包各个重量的最优解dp[j]，从第一个物品到最后一个物品，背包空间初始为M（题目给定的值），放入第i件物品，空间减少w[i]，价值增加v[i]，不断更新直到背包空间为0。 状态更新公式：dp[j]=max(dp[j],dp[j-w[i]]+v[i]

AC代码

#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <sstream> using namespace std; int n,m; int v[13000];//价值 int w[13000];//重量 int dp[13000]; int main() { memset(dp,0,sizeof(dp));//初始化都为0 cin >> n >> m; for(int i=0; i<n; i++) cin >> w[i] >> v[i]; for(int i=0; i<=n; i++)//从第0到第n-1件物品 { for(int j=m; j>=w[i]; j--)//dp更新中，保证j-w[i]必须大于0，即背包空间一直大于0 dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } cout << dp[m]; return 0; }