典型01背包问题,,分解成子问题,一个珠子最大重量m求最大等级、两个珠子最大重量m求最大等级··········dp用一个数组就行了,随珠子数量增加而刷新
对每个珠子只有两种选择,取或不取,所以状态转移方程是 dp[j]=max(dp[j],dp[j-w[i]]+d[i])
#include <stdio.h> #include <string.h> #define MAX(a,b) (a)>(b)?(a):(b); int main() { int n, m,w[3405],d[3405],dp[12881]; scanf("%d%d", &n, &m); for (int i = 0; i < n; i++){ scanf("%d%d", &w[i], &d[i]); } memset(dp, 0, sizeof(dp)); for (int i = 0; i < n; i++){ for (int j = m; j >= w[i]; j--){ dp[j] = MAX(dp[j], dp[j - w[i]]+d[i]); } } printf("%d\n", dp[m]); return 0; }