[USACO07DEC]手链Charm Bracelet 【01背包】

本人水平有限，题解不到为处，请多多谅解

本蒟蒻谢谢大家观看

经典的01背包

直接上模板。

code:

 1 #include<bits/stdc++.h>
 2 #pragma GCC optimize(3)
 3 const int N=1e5+100;
 4 using namespace std;
 5 int n,v,sum;
 6 int val[N],c[N];
 7 int f[N];
 8 inline int read(){
 9     int x=0,f=1;char ch=getchar();
10     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
11     while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
12     return x*f;
13 }
14 inline void write(int x){
15      char F[200];
16      int tmp=x>0?x:-x ;
17      if(x<0)putchar('-') ;
18      int cnt=0 ;
19         while(tmp>0)
20         {
21             F[cnt++]=tmp%10+'0';
22             tmp/=10;
23         }
24         while(cnt>0)putchar(F[--cnt]) ;
25 }
26 int main()
27 {
28     n=read(),v=read();
29     for(int i=1;i<=n;i++){
30         c[i]=read(),val[i]=read();
31         sum+=c[i];
32     }
33     memset(f,0,sizeof(f));
34     f[0]=0;//一定要初始化 
35     for(int i=1;i<=n;i++){
36         for(int j=v;j>=c[i];j--){//要写逆循环，因为每件物品只能出现一次 
37             f[j]=max(f[j],f[j-c[i]]+val[i]);
38         }
39     }
40     printf("%d
",f[v]);
41     return 0;
42 }