poj1741，POJ 3624 Charm Bracelet(01背包 基礎)

題意： n個裝飾品 容量m的背包

???????? 每個裝飾品 重wi 價值 di

??????? 求能裝的最大價值

思路：基礎01背包

?

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;int dp[13880];
int main()
{int n,m;int i,j;int w,d;int maxx;while(scanf("%d%d",&n,&m)!=EOF){mem(dp,-1);dp[0]=0;maxx=0;while(n--){scanf("%d%d",&w,&d);for(i=m;i>=w;i--){if(dp[i-w]!=-1&&dp[i-w]+d>dp[i]){dp[i]=dp[i-w]+d;if(dp[i]>maxx) maxx=dp[i];}}}      printf("%d\n",maxx);}return 0;
}