#　题目
<blockquote>
<h2 id="description">Description</h2>
<blockquote>
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.
 
</blockquote>
<h2 id="input">Input</h2>
<blockquote>
<ul>
<li>Line 1: Two space-separated integers: N and M</li>
<li>Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di</li>
</ul>
</blockquote>
<h2 id="output">Output</h2>
<blockquote>
<ul>
<li>Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints</li>
</ul>
</blockquote>
<h2 id="sample-input">Sample Input</h2>
<blockquote>
4 6 
1 4 
2 6 
3 12 
2 7
</blockquote>
<h2 id="sample-output">Sample Output</h2>
<blockquote>
23
</blockquote>
</blockquote>
<h1 id="heading">题解</h1>
模板题,<a href="/post/Algorithm/Package_Problem.html#01%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98">01背包问题</a>
<h1 id="heading-1">代码</h1>
<pre style="background-color:#fff">/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com
 
かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
 
#include &lt;cstdio&gt;
#include &lt;algorithm&gt;
#include &lt;cstring&gt;
#include &lt;cmath&gt;
#include &lt;string&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;list&gt;
#include &lt;queue&gt;
#include &lt;stack&gt;
#include &lt;map&gt;
#include &lt;set&gt;
using namespace std;
 
const int maxn = 20000;
int dp[maxn];
int v;
 
void ZeroOnePack(int cost,int weight) {
 for(int i = v; i &gt;= cost; i--)
 dp[i] = max(dp[i],dp[i - cost] + weight);
}
 
bool Do() {
 int n,m;
 if(scanf(&#34;%d%d&#34;,&amp;n,&amp;m) == EOF)
 return false;
 
 v = m;
 memset(dp,0,sizeof(dp));
 
 for(int i = 1;i &lt;= n;i++) {
 int a,b;
 scanf(&#34;%d%d&#34;,&amp;a,&amp;b);
 ZeroOnePack(a,b);
 }
 
 printf(&#34;%d\n&#34;,dp[m]);
 return true;
}
 
int main() {
 while(Do());
 return 0;
}
</pre>

AOJ 275.Charm Bracelet