FZU 2214

Given a set of n items, each with a weight w[i] and a value v[i], determine a way to choose the items into a knapsack so that the total weight is less than or equal to a given limit B and the total value is as large as possible. Find the maximum total value. (Note that each item can be only chosen once).

The first line contains the integer T indicating to the number of test cases.

For each test case, the first line contains the integers n and B.

Following n lines PRovide the information of each item.

The i-th line contains the weight w[i] and the value v[i] of the i-th item respectively.

1 <= number of test cases <= 100

1 <= n <= 500

1 <= B, w[i] <= 1000000000

1 <= v[1]+v[2]+...+v[n] <= 5000

All the inputs are integers.

For each test case, output the maximum value.

15 1512 42 21 14 101 2Sample Output
15
常規的01背包，不過背包容量的范圍為1000000000，使用常規的01代碼會數組越界。
題解：將價值和重量反過來考慮，求關于價值的數組f[5010]，對于某個價值的最小容量，要求背包必須裝滿，最后從最大價值開始向前遍歷，直至找到符合題意的容量
include<iostream>#include<cmath>#include<cstring>#include<cstdio>#include<vector>#include<algorithm>#define inf 0x3f3f3f3f#define ll long longusing namespace std;int w[510];int v[510];int f[5010];int main(){    int T;    cin>>T;    while(T--)    {        int n,g;        cin>>n>>g;        int sumv=0;        for(int i=1;i<=n;i++)        {            scanf("%d%d",&w[i],&v[i]);            sumv+=v[i];        }        f[0]=0;        for(int i=1;i<=5010;i++)            f[i]=inf;        for(int i=1;i<=n;i++)            for(int j=sumv;j>=v[i];j--)                f[j]=min(f[j],f[j-v[i]]+w[i]);        for(int i=sumv;i>=0;i--)            if(f[i]<=g)        {            cout<<i<<endl;            break;        }    }    return 0;}poj 3628
Farmer John recently bought another bookshelf for the cow library, but the shelf is getting filled up quite quickly, and now the only available space is at the top.
FJ has N cows (1 ≤ N ≤ 20) each with some height ofHi (1 ≤Hi ≤ 1,000,000 - these are very tall cows). The bookshelf has a height ofB (1 ≤B ≤ S, where S is the sum of the heights of all cows).
To reach the top of the bookshelf, one or more of the cows can stand on top of each other in a stack, so that their total height is the sum of each of their individual heights. This total height must be no less than the height of the bookshelf in order for the cows to reach the top.
Since a taller stack of cows than necessary can be dangerous, your job is to find the set of cows that produces a stack of the smallest height possible such that the stack can reach the bookshelf. Your program should print the minimal 'excess' height between the optimal stack of cows and the bookshelf.
Input
* Line 1: Two space-separated integers: N andB* Lines 2..N+1: Line i+1 contains a single integer: Hi
Output
* Line 1: A single integer representing the (non-negative) difference between the total height of the optimal set of cows and the height of the shelf.
Sample Input
5 1631356Sample Output
1
題意：n頭牛，每頭牛有一個高度hi，書架高度為b，求任意選擇某些牛加起來的高度比書架高的部分最小
題解：使用01背包，w數組和v數組相同，即對于某個高度h，f[h]=(當前奶牛雖能達到的<=h的最大高度),
最后從f[b]開始遍歷，找到f[]>=b的下標
#include<iostream>#include<cmath>#include<cstring>#include<cstdio>#include<algorithm>#define inf 0x3f3f3f3f#define ll long longusing namespace std;int w[30];int f[10000010];int main(){    int n,b;    while(cin>>n>>b)    {        int sum=0;        for(int i=1;i<=n;i++)        {            cin>>w[i];            sum+=w[i];        }        memset(f,0,sizeof(f));        for(int i=1;i<=n;i++)            for(int j=sum;j>=w[i];j--)                f[j]=max(f[j],f[j-w[i]]+w[i]);        int ans;        for(int i=b;i<=sum;i++)            if(f[i]>=b)        {            ans=f[i];            break;        }        cout<<ans-b<<endl;    }    return 0;}
hdu 2546
   電子科大本部食堂的飯卡有一種很詭異的設計，即在購買之前判斷余額。如果購買一個商品之前，卡上的剩余金額大于或等于5元，就一定可以購買成功（即使購買后卡上余額為負），否則無法購買（即使金額足夠）。所以大家都希望盡量使卡上的余額最少。某天，食堂中有n種菜出售，每種菜可購買一次。已知每種菜的價格以及卡上的余額，問最少可使卡上的余額為多少。 Input多組數據。對于每組數據： 第一行為正整數n，表示菜的數量。n<=1000。 第二行包括n個正整數，表示每種菜的價格。價格不超過50。 第三行包括一個正整數m，表示卡上的余額。m<=1000。 n=0表示數據結束。 Output對于每組輸入,輸出一行,包含一個整數，表示卡上可能的最小余額。Sample Input
1505101 2 3 2 1 1 2 3 2 1500Sample Output
-4532題意：卡上的剩余金額大于或等于5元，就一定可以購買成功（即使購買后卡上余額為負），否則無法購買（即使金額足夠）。所以大家都希望盡量使卡上的余額最少。 食堂中有n種菜出售，每種菜可購買一次。已知每種菜的價格以及卡上的余額，問最少可使卡上的余額為多少。 
題解：先用剩下的5元錢買最貴的菜，剩下的45元為01背包，剔除剛剛用過的那個物品，01背包中w[]與v[]相同，f[45]為45元錢可以買到的最大價值的菜，m-5-f[45]
#include<iostream>#include<cmath>#include<cstring>#include<cstdio>#include<algorithm>#define inf 0x3f3f3f3f#define ll long longusing namespace std;int f[50010];int w[1010];int main(){    int n;    while(cin>>n)    {        if(n==0)            return 0;        for(int i=1;i<=n;i++)            cin>>w[i];        int m;        cin>>m;        if(m<5)            cout<<m<<endl;        else        {        sort(w+1,w+n+1);        memset(f,0,sizeof(f));        for(int i=1;i<=n-1;i++)            for(int j=m-5;j>=w[i];j--)            f[j]=max(f[j],f[j-w[i]]+w[i]);        cout<<m-w[n]-f[m-5]<<endl;        }    }    return 0;}