宁波市网站建设_网站建设公司_内容更新_seo优化

题目链接

洛谷 P2871 [USACO07DEC] Charm Bracelet S

思路分析

0-1 背包模板题，详见洛谷 P1048 [NOIP 2005 普及组] 采药 题解。

代码呈现

#include<bits/stdc++.h>
using namespace std;const int N=3405,M=12885;
int n,m;
int w[N],d[N],dp[M];int main(){scanf("%d%d",&n,&m);for (int i=1;i<=n;++i) scanf("%d%d",w+i,d+i);for (int i=1;i<=n;++i){for (int j=m;j>=w[i];--j) dp[j]=max(dp[j],dp[j-w[i]]+d[i]);}printf("%d",dp[m]);return 0;
}