Charm Bracelet(0-1)
生活随笔
收集整理的這篇文章主要介紹了
Charm Bracelet(0-1)
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
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?iin 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.
Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi?and Di
AC代碼：
#include<bits/stdc++.h> using namespace std; int main() {int T,M,i,s;int a[40000],b[40000],c[40000];while(cin>>M>>T){for(i=1;i<=M;i++)cin>>a[i]>>b[i];memset(c,0,sizeof(c));for(i=1;i<=M;i++)for(s=T;s>=a[i];s--)if(c[s]<c[s-a[i]]+b[i])c[s]=c[s-a[i]]+b[i];cout<<c[T]<<endl;}return 0; }
總結
以上是生活随笔為你收集整理的Charm Bracelet(0-1)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： N的阶乘末尾有多少个0
- 下一篇： blockhouses