01背包问题

这个博主动态规划讲的十分详细：

https://blog.csdn.net/shanghairuoxiao/article/details/62426727

1.算法提高 01背包  

题目链接：

http://lx.lanqiao.cn/problem.page?gpid=T287

这是蓝桥杯的一个模板题，非常简单就不多说了。

#include <iostream>
#include <cstdio>

using namespace std;
const int MX = 5000+10;
int v[MX], val[MX];
int dp[MX];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d %d", &v[i], &val[i]);
    for(int i = 1; i <= n; ++i)
        for(int j = m; j >= v[i]; --j)
            dp[j] = max(dp[j], dp[ j-v[i] ]+val[i]);
    printf("%d
", dp[m]);
}

2.HDU2546：饭卡

题目链接：

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

这道题也是经典的01背包问题，不过有点变式，读懂题目后知道其要求我们背包完后用剩下的5元买最贵的那个：

AC代码如下：

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>

using namespace std;
const int MX = 1000+10;
int v[MX];
int dp[MX];

int main()
{
    int n, m;
    while(scanf("%d", &n) != EOF && n != 0)
    {
        memset(v, 0, sizeof(v));
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; ++i) scanf("%d", &v[i]);
        sort(v+1, v+n+1);
        scanf("%d", &m);
        if(m < 5) //注意特判一下
        {
            printf("%d
", m);
            continue;
        }
        m -= 5;
        for(int i = 1; i < n; ++i)
            for(int j = m; j >= v[i]; --j)
                dp[j] = max(dp[j], dp[ j-v[i] ]+v[i]);
        int ans = m+5-v[n]-dp[m];
        printf("%d
", ans);
    }
}

3.HDU - 2602 Bone Collector

题目链接：

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

这个题目和蓝桥杯的题目一样，是一道模板题。不多说了，直接上代码。

AC代码：

#include <iostream>
#include <cstdio>
#include <string.h>

using namespace std;
const int MX = 1000+10;
int v[MX], val[MX];
int dp[MX];

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        memset(v, 0, sizeof(v));
        memset(val, 0, sizeof(val));
        memset(dp, 0, sizeof(dp));
        int n, m;
        scanf("%d%d", &n , &m);
        for(int i = 1; i <= n; ++i) scanf("%d", &val[i]);
        for(int i = 1; i <= n; ++i) scanf("%d", &v[i]);
        for(int i = 1; i <= n; ++i)
            for(int j = m; j >= v[i]; --j)
            {
                dp[j] = max(dp[j], dp[ j-v[i] ]+val[i]);
            }
        printf("%d
", dp[m]);
    }
}

4.HDU - 1171  Big Event in HDU

题目链接：

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

这道题有点意思。

大致题意是：给你不同的设施，每个设施都有自己的价值，相同价值的设施会一起给你。（这里要用while统计一下）。

最后得到一个最佳的方案，输出2个学院分到的价值。

要注意的是这里的最大价值m，也就是背包的容量应该为sum/2。因为应该使方案最接近平均分。

AC代码如下：

#include <iostream>
#include <cstdio>
#include <string.h>

using namespace std;
const int MX = 100000+10;
int dp[MX];
int val[MX];

int main()
{
    int T;
    while(scanf("%d", &T) != EOF && T > 0)
    {
        memset(dp, 0, sizeof(dp));
        memset(val, 0, sizeof(val));
        int k = 0;
        int sum = 0;
        while(T--)
        {
            int x, t;
            scanf("%d%d", &x, &t);
            while(t--)
            {
                val[k++] = x;
                sum += x;
            }
        }
       // printf("%d %d
", sum, val[k-1]);
        for(int i = 0; i < k; ++i)
            for(int j = sum/2; j >= val[i]; --j)
            {
                dp[j] = max(dp[j], dp[ j-val[i] ]+val[i]);
            }
        printf("%d %d
", sum-dp[sum/2] ,dp[sum/2]);
    }
}

5.HDU - 1864 最大报销额

题目链接：

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

这一题和Big event in HDU 有点像。

题目大意：一行代表了一张支票，输入格式为：m Type_1:price_1 Type_2:price_2 ... Type_m:price_m
其中正整数 m 是这张发票上所开物品的件数，Type_i 和 price_i 是第 i 项物品的种类和价值。也就是说m为一张支票中项目的个数，并且支票内总价要小于1000.00，同时只能报销type为A, B, C的，每种type的总价要低于600.00。

这题输入格式需要注意！scanf(" %c: %lf", &c, &x);有空格！！！

下面是AC代码：注意格式！和数组大小！

#include <iostream>
#include <cstdio>
#include <string.h>

using namespace std;
const int MX = 3e6+10;
double dp[MX];
double val[100+10];
double type[4];
int main()
{
    int n;
    double m;
    while(scanf("%lf%d", &m, &n) != EOF && n)
    {
        memset(dp, 0, sizeof(dp));
        memset(val, 0, sizeof(val));
        int k = 0;

        for(int i = 1; i <= n; ++i)
        {
            memset(type, 0, sizeof(type));
            double sum = 0;
            int t;
            bool flag = true;
            scanf("%d", &t);
            while(t--)
            {
                char c;
                double x;
                scanf(" %c: %lf", &c, &x);
                sum += x;
                if(c != 'A' && c != 'B' && c != 'C')
                {
                    flag = false;
                    continue;
                }
                type[c-'A'] += x;
                if(sum > 1000 || type[c-'A'] > 600) flag = false;
            }
            if(flag) val[k++] = sum;
            //printf("%lf
", val[k]);
        }
        for(int i = 0; i < k; ++i)
            for(int j = (int)(m*100); j >= (int)(val[i]*100); --j)
            {
                dp[j] = max((int)dp[j], (int)dp[ j-(int)(val[i]*100) ]+(int)(val[i]*100));
            }
        printf("%.2lf
", dp[(int)(m*100)]/100.00);
    }
}

如有疑问，欢迎评论指出！