背包DP FOJ 2214

题目：http://acm.fzu.edu.cn/problem.php?pid=2214

（http://www.fjutacm.com/Problem.jsp?pid=2053）

这题看起来是一题普通背包题，但是你会发现相对价格来说，体积太大了，此时只要将体积看为价格，价格看为体积，然后再来一个普通的背包DP算法就好了；

#include<stdio.h>
#include<algorithm>
using namespace std;
struct N
{
    int w, v;
}a[610];
int dp[5050];
int main( )
{
    int n, t, i, j, V, r;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &V);
        for(i=r=0; i<n; i++)
            scanf("%d%d", &a[i].w, &a[i].v), r+=a[i].v;
        for(i=1; i<=r; i++)
            dp[i]=1e9;
        for(i=dp[0]=0; i<n; i++)
            for(j=r; j>=a[i].v; j--)
                dp[j]=min(dp[j], dp[j-a[i].v]+a[i].w);
        for(i=1, j=0; i<=r; i++)
            if(dp[i]<=V&&j<i)
                j=i;
        printf("%d
", j);
    }
}