DP：poj 3624 Charm Bracelet (0-1双肩包)

DP：poj 3624 Charm Bracelet (0-1背包)

【转】http://blog.****.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;
}