题目训练（密码hpuacm）：https://vjudge.net/contest/244922

背包问题有 部分背包 01背包完全背包多重背包

部分背包是一种可分割的背包，就是一个背包我们可以只取它的部分。那么给出一组物品的价值和重量，怎么选才能让背包装的价值最大呢？很简单，选性价比最高的，即优先选择的是单位重量价值（v[i] / w[i]）最高的那个。

01背包就很熟悉了，就是给出一系列的物品，每个物品只有选和不选两个状态，故称为01背包。

完全背包则是在01背包的基础上，每个物品可以挑选任意件，问背包能装的最大价值。

多重背包则是每个物品有c[i]个，每个物品能选0 - c[i] 个，问最大价值。

FatMouse' Trade

肥鼠准备了 M 磅的猫粮，准备和看管仓库的猫交易，仓库里装有他最喜爱的食物 Java 豆。

仓库有 N 个房间。第 i 间房包含了 J[i] 磅的 Java 豆，需要 F[i] 磅的猫粮。肥鼠不必为了房间中的所有 Java 豆而交易，相反，他可以支付 F[i] * a% 磅的猫粮去交换得到 J[i] * a% 磅的 Java 豆。这里，a 表示一个实数。

现在他将这项任务分配给了你：请告诉他，能够获得的 Java 豆的最大值是多少。

输入

输入包含多组测试数据。

对于每组测试数据，以包含了两个非负整数 M 和 N 的一行开始。接下来的 N 行，每行相应包含了两个非负整数 J[i] 和 F[i]。

最后一组测试数据是两个 -1。所有的整数均不超过 1000。

输出

对于每组测试数据，在单独的一行中打印一个实数，精确到小数点后 3 位数，表示肥鼠能够取得的 Java 豆的最大值。

示例输入

5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1

示例输出

13.333
31.500

这道题很明显就是一个部分背包的问题，其思想是贪心，不是DP

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000 + 10;
struct node{
    int j, f;
    double val;
};
struct node num[MAXN];
bool cmp( struct node n1, struct node n2 )
{
    return n1.val > n2.val;
}
int main()
{
    int m, n;
    while( scanf("%d%d", &m, &n), (m != -1 || n != -1) )
    {
        for( int i=0; i<n; i++ )
        {
            scanf("%d%d", &num[i].j, &num[i].f);
            num[i].val = 1.0 * num[i].j / num[i].f;
        }
        sort(num, num + n, cmp);
        double ans = 0;
        for( int i=0; i<n && m > 0; i++ )
        {
            if( num[i].f <= m )
            {
                ans += 1.0 * num[i].j;
                m = m - num[i].f;
            }
            else if( num[i].f > m )
            {
                ans += 1.0 * num[i].j * ( 1.0 * m / num[i].f );
                m = 0;
            }
        }
        printf("%.3lf\n", ans);
    }

    return 0;
}

Bone Collector

涂奥最近迷上了吃鸡，房间有n个配件，每个配件有c(c<=1e3)的重量和v(v<=1e3)的价值，哇，涂奥捡了一个2级包，容量为s，所以涂奥最多当多肥的快递员呢？

Input

输入的第一行是T, 表示有一共要打T场比赛.

每组数据由三行组成.

第1行包含两个整数n和s 第2行包含n个整数, 表示每一个配件的价值. 第3行包含n个整数, 表示每个配件的重量.

Output

对每一组数据, 输出涂奥可以多肥.

Sample Input

1
10 10
1 3 5 7 9 11 13 15 17 19
19 17 15 13 11 9 7 5 3 1

Sample Output

明显的01背包问题 dp[i+1][j] : 从0到 i 这 i +1个物品所选的总价值不超过 j 的最大价值

#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int) 1e3+7;

int dp[MAXN][MAXN];
int c[MAXN];
int v[MAXN];
int main()
{
    int t;
    scanf("%d", &t);
    while( t-- )
    {
        int n, s;
        scanf("%d%d", &n, &s);
        for( int i=0; i<n; i++ )
            scanf("%d", &v[i]);
        for( int i=0; i<n; i++ )
            scanf("%d", &c[i]);
        memset(dp, 0, sizeof(dp));
        for( int i=0; i<n; i++ )
        {
            for( int j=0; j<=s; j++ )
            {
                if( j < c[i] )
                    dp[i+1][j] = dp[i][j];
                else
                    dp[i+1][j] = max(dp[i][j], dp[i][j - c[i]] + v[i]);
            }
        }
        printf("%d\n", dp[n][s]);
    }

    return 0;
}

悼念512汶川大地震遇难同胞——珍惜现在，感恩生活

这道题是一个模板式的多重背包问题，优化部分用到了二进制分解，以后会详解

这个题博主的水平也有限，一直想改成二维的dp，但始终没成功。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100+10;

int dp[MAXN*MAXN];
int v[MAXN], w[MAXN], c[MAXN];  // 大米的价值，重量和数量
int main()
{
    int t;
    scanf("%d", &t);
    while( t-- )
    {
        int n, m;
        scanf("%d %d", &n, &m);
        for( int i=0; i<m; i++ )
            scanf("%d%d%d", &v[i], &w[i], &c[i]);
        memset(dp, 0, sizeof(dp));
        for( int i=0; i<m; i++ )
        {
            int num = c[i];
            for( int k=1; num > 0; k = k << 1 )
            {
                int mul = min(k, num);
                for( int j = n; j >= v[i] * mul; j-- )
                    dp[j] = max(dp[j], dp[j - v[i] *mul] + w[i] *mul);
                num -= mul;
            }
        }
        printf("%d\n", dp[n]);
    }

    return 0;
}

动态规划之背包问题（待完善）

FatMouse' Trade

Bone Collector

悼念512汶川大地震遇难同胞——珍惜现在，感恩生活