4 6
1 4 2 6 3 12 2 7
// poj 3624 标准的01背包 优化的一位数组
#include <iostream>
#include <string.h>
using namespace std;
int w[3500],v[3500],dp[13000];
int main ()
{ int n,m,i,j;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]);
memset(dp,0,sizeof(dp));
for (i=1;i<=n;i++)
for (j=m;j>=w[i];j--)
if (dp[j]<dp[j-w[i]]+v[i]) dp[j]=dp[j-w[i]]+v[i];
printf("%d\n",dp[m]);
return 0;
}
// poj 3624 标准的01背包 优化的一位数组
#include <stdio.h>
int main()
{
int n, v, i, j, ans, c[3403], w[3403], f[12881];
scanf("%d %d", &n, &v);
for (i = 1; i <= n; i++) scanf("%d %d", &c[i], &w[i]);
for (i = 0; i <= v; i++) f[i] = 0;
for (i = 1; i <= n; i++)
for (j = v; j >= c[i]; j--)
if (f[j - c[i]] + w[i] > f[j]) f[j] = f[j - c[i]] + w[i];
ans = 0;
for (i = 1; i <= v; i++)
if (f[i] > ans) ans = f[i];
printf("%d\n", ans);
return 0;
}
原文：http://www.cnblogs.com/2014acm/p/3920247.html
