学步园

 因为某位同学最近在学背包，还老是问我问题，然后我就被拉去一起写背包问题了，不过也好，把以前的不会写的恰好装满的背包问题给写了。

其实还是挺好的。。。下面来说一说吧：

首先，你要把普通的背包熟悉（高深的我也不会了），然后如果是求最小值的恰好装满背包，那就先   int   INF = 1000000;  然后全部的初始化为 - INF，dp[1] = 0;  这样就可以了，类似的，当求最大值的恰好装满背包，那就全部初始化为INF
即可。

 题目号  TOJ  3232   TOJ 礼品兑换 
杭电 HDU 1114 Piggy-Bank

下面来两道例题吧

http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=3232 

这题是典型的多重背包，取最大值

#include<stdio.h>
#include<string.h>

const int N = 110;
const int INF = 10000000;    // 尽量定义的大一点，具体多大，我也不知道，应该这么大就可以了吧
int dp[100010];
int c[N], v[N];


int max(int x, int y)
{
    return x > y ? x : y;
}

int main()
{
    int n;
    int x, y, i, j;
    while(~scanf("%d",&n))
    {
        while(n--)
        {       
            scanf("%d%d",&x,&y);
            int price, weight, sum;
            int cnt= 1;
            for (i = 1; i <= y; i ++)                  // 用二进制的多重背包的方法
            {
                scanf("%d%d%d",&price, &sum, &weight);
                int t = 1;
                while(sum >= t)
                {
                    c[cnt] = t * price;
                    v[cnt++] = t * weight;
                    sum =sum - t;
                    t = t << 1;
                }
                if(sum)
                {
                    c[cnt] = sum * price;
                    v[cnt++] = sum * weight;
                }
            }
            for(i = 0; i <= x; i ++)
                dp[i] = - INF;                      // 初始化要注意
            dp[0] = 0;
            for (i = 1 ; i < cnt ; i ++ )
            {
                for(j = x; j >= v[i]; j --)
                dp[j] = max(dp[j], dp[j - v[i]] + c[i]);
            }
            if(dp[x] < 0)
                printf("This is impossible.\n");
            else
                printf("The maximum value is %d.\n",dp[x]);
        }
    }   
    return 0;
}

这题是杭电的01 - 背包 ， 是取最小值的

http://acm.hdu.edu.cn/showproblem.php?pid=1114

#include <stdio.h>

const int N = 550;
int c[N];
int w[N];
int dp[10010];
const int INF = 10000000;

int min(int x, int y)
{
    return x < y ? x : y ;
}

int main()
{
    int n, m;
    int i, j;
    int a, b;
    int cc, ww;
    while(~scanf("%d",&n))
    {
        while(n --)
        {
            scanf("%d%d", &cc, &ww);
            scanf("%d", &m);
            for(i = 0; i <= ww - cc; i ++)
                dp[i] = INF;
            for(i = 0; i < m; i ++)
                scanf("%d%d",&c[i], &w[i]);
            dp[0] = 0;
            for(i = 0;i < m; i ++)
            {
                for(j = w[i]; j <= ww - cc; j ++)
                    dp[j] = min(dp[j - w[i]] + c[i], dp[j]);
            }
            if(dp[ww - cc] == INF)
                printf("This is impossible.\n");  
            else  
                printf("The minimum amount of money in the piggy-bank is %d.\n",dp[ww - cc]);  
        }
    }
    return 0;
}