DP：poj 3624 Charm Bracelet (0-1背包)
【转】http://blog.csdn.net/zxy_snow/article/details/6003790
?
一维：
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
using namespace std;
int bag[12900];
int w[3410],v[3410];
int main(void)
{
?int n,m;
?cin >> n >> m;
?for(int i=1; i<=n; i++)
??cin >> w[i] >> v[i];
?memset(bag,0,sizeof(bag));
?for(int i=1; i<=n; i++)?
??for(int k=m; k>=w[i]; k--)
???if( bag[k-w[i]]+ v[i] > bag[k] )
????bag[k] = bag[k-w[i]]+ v[i];
?cout << bag[m] << endl;
return 0;
}
?
二维：
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
using namespace std;
int bag[100][100];
int w[3410],v[3410];
int main(void)
{
?int n,m;
?cin >> n >> m;
?for(int i=1; i<=n; i++)
??cin >> w[i] >> v[i];
?memset(bag,0,sizeof(bag));
?for(int i=1; i<=n; i++)?
??for(int k=1; k<=m; k++)
???if( k >= w[i])
???{
????if(?bag[i-1][k-w[i]]+ v[i] > bag[i-1][k] )
?????bag[i][k] = bag[i-1][k-w[i]]+ v[i];
????else
?????bag[i][k] = bag[i-1][k];
???}
???else
????bag[i][k] = bag[i-1][k];
?cout << bag[n][m] << endl;
return 0;
}
