问题描述：
总共有N种宝石供挑选，宝石i的重量为Wi,吸引力为Di，只可以用一次。Bessie最多可负担的宝石手镯总重量为M。给出N，M，Wi，Di，求M。
非常标准的01背包问题。使用了优化的一维数组的代码。因为对于这类问题，只有i-1的f[v]对计算i的f[v]有用，所以使用一维数组的时候相当于将原来i-1之前的记录覆盖掉。
下边是我的代码：
#include<iostream>
#include<string.h>
#include<stdio.h>
#define M 12880+10
using namespace std;
int f[M];
int w[],d[];
int main(){
int n,m;
scanf("%d%d",&n,&m);
memset(f,,sizeof(f));
for(int i=;i<n;i++){
scanf("%d%d",w+i,d+i);
}
for(int i=;i<n;i++){
for(int j=m;j>=w[i];j--){
if(f[j]<f[j-w[i]]+d[i]){
f[j]=f[j-w[i]]+d[i];
}
}
}
printf("%d\n",f[m]);
return ;
}
算法的时间复杂度为O(MN),空间复杂度为O(M);