背包问题拓展应用

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;}