NYOJ--860 又见01背包（01背包）

题目http://acm.nyist.net/JudgeOnline/problem.php?pid=860

分析：题目和普通的01背包问题一样，但是唯一不同的是数据的特殊性。

如果10^9根本就开辟不了这么大的数组。于是这里我们就把

重量和价值互换。

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;

const int INF=0X3F3F3F3F;   //这里初始化一定要很大

int main()
{
  int n,W,w[102],v[102],dp[10010],sum;
  while (scanf("%d%d",&n,&W)!=EOF)
  {
    sum=0;
    for(int i=1;i<=n;i++)
    {
      scanf("%d%d",&w[i],&v[i]);
      sum+=v[i];
    }
    //INF如果过小 很一直过不了！
    for(int i=0;i<=sum;i++) dp[i]=INF;
    dp[0]=0;
    
    
    for(int i=1;i<=n;i++)
      for(int j=sum;j>=v[i];j--)
        dp[j]=min(dp[j],dp[j-v[i]]+w[i]);

    for(int i=sum;i>=0;i--)
    if(dp[i]<=W) {printf("%d ",i);break;}

  }
  return 0;
}

来自为知笔记(Wiz)