洛谷背包专题

普及组

P1734

思路

• 01背包模板套用
• 1 < i < s的数就是物品的体积
• 其中sum保留每个数i的约数之和，也就是物品的价值

代码演示

#include <stdio.h>

inline int read() {
    int w = 0, x = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    
    return w ? -x : x;
}

#define MAX_S 1001

int sum[MAX_S];

//预处理每个物品的价值 
inline void init(int s) { 
    
    for (int i = 2; i < s; i++) {
        sum[i] = 1;
        for (int j = 2; j < i; j++) {
            if ((j << 1) > i) break;
            if (i % j == 0) sum[i] += j;
        }
    }
//    for (int i = 1; i < s; i++) {
//        printf("%d\n", sum[i]);
//    }
    return ;
}
int s;
int dp[MAX_S];
#define max(a, b) ({\
    (a) > (b) ? (a) : (b);\
})

int main() {
    s = read();
    init(s);

    for (int i = 2; i < s; i++) { //枚举背包体积vi == i 
        for (int j = s; j; j--) {
            if (j >= i) {
                dp[j] = max(dp[j], dp[j - i] + sum[i]);
            }
        }
    }
    printf("%d\n", dp[s]);
    return 0;
}

P1926 小书童——刷题大军

思路

• 两个01背包
• 分别求得每个时间得到的最大分数与刷题的最大数量

代码演示

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

inline int read() {
    int x = 0, w = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -x : x;
}

#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))


int t[11];    //代表每“题”他的需要时间
int task[11]; //表示每项作业它的需要时间
int score[11]; //代表每项作业它的分值
int dp[151]; //记录每个时间得到的最大分数 
int ans[151];  //记录每个时间刷的最大题量 

int main() {
    int n, m, k, r;
    n = read(), m = read(), k = read(), r = read();
    
    for (int i = 1; i <= n; i++) {
        t[i] = read();
    }
    for (int i = 1; i <= m; i++) {
        task[i] = read();
    }
    for (int i = 1; i <= m; i++) {
        score[i] = read();
    }
    for (int i = 1; i <= m; i++) {
        for (int j = r; j >= task[i]; j--) {
            dp[j] = max(dp[j], dp[j - task[i]] + score[i]);
        }
    }
    int tp;
    for (int i = 1; i <= r; i++) {
        //printf("dp[%d] = %d\n", i, dp[i]);
        if (dp[i] >= k) {
            tp = i;
            break;
        }
    }
    //printf("%d\n", tp);
    //printf("%d\n", r - tp);
//    memset(ans, 0, sizeof(ans));
    
    for (int i = 1; i <= n; i++) {
        for (int j = r - tp; j >= t[i]; j--) {
        //    printf("ans[%d] = %d\n", j, ans[j]);
            ans[j] = max(ans[j], ans[j - t[i]] + 1);
        //    printf("ans[%d] = %d\n", j, ans[j]);
        }
    }
    printf("%d\n", ans[r - tp]);
    
    return 0;
}

P1049 [NOIP2001 普及组] 装箱问题

思路

• 01背包直接用

代码演示

#include <stdio.h>
inline int read() {
    int x = 0, w = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -x : x;
}

#define max(a, b) ({\
    (a) > (b) ? (a) : (b);\
})

int dp[20004];

int V, n;
int main() {
    V = read(), n = read();
    for (int v, i = 1; i <= n; i++) {
        v = read();
        for (int j = V; j >= v; j--) {
            dp[j] = max(dp[j], dp[j - v] + v);
        }
    }
    printf("%d\n", V - dp[V]);
    return 0;
} 

P2639 [USACO09OCT]Bessie’s Weight Problem G

思路

• 01背包模板

代码演示

#include <stdio.h>
inline int read() {
    int x = 0, w = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -x : x;
}

#define max(a, b) ({\
    (a) > (b) ? (a) : (b);\
})

int dp[45003];

int V, n;
int main() {
    V = read(), n = read();
    for (int v, i = 1; i <= n; i++) {
        v = read();
        for (int j = V; j >= v; j--) {
            dp[j] = max(dp[j], dp[j - v] + v);
        }
    }
    printf("%d\n", dp[V]);
    return 0;
} 

P1048 [NOIP2005 普及组] 采药

思路

• 01背包模板套用
• 没有思路可言

代码演示

#include <stdio.h>
inline int read() {
    int x = 0, w = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar(); 
    }
    return w ? -x : x;
}

#define max(a, b) ((a) > (b) ? (a) : (b))

#define MAX_T 1001


int dp[MAX_T];
int T, M;

int main() {
    T = read(), M = read();
    for (int t, w, i = 1; i <= M; i++) {
        t = read(), w = read();
        for (int j = T; j; j--) {
            if (j >= t) dp[j] = max(dp[j], dp[j - t] + w);
        }
    }
    printf("%d\n", dp[T]);
    return 0;
}

P1060 [NOIP2006 普及组] 开心的金明

思路

• 01背包模板套用
• 1 < vi < s的数就是物品的体积，也就是题目的物品的价格
• vi * wi为物品的价值，其中wi为题目物品的重要度

代码演示

#include <stdio.h>
inline int read() {
    int w = 0, x = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar(); 
    }
    return w ? -x : x;
}
#define max(a, b) ((a) > (b) ? (a) : (b))

#define MAX_N 30004

int dp[MAX_N];
int n, m;

int main() {
    n = read(), m = read();
    //01背包模板套用 
    for (int v, w, i = 1; i <= m; i++) {
        v = read(), w = read();
        for (int j = n; j; j--) {
            if (j >= v) {
                dp[j] = max(dp[j], dp[j - v] + v * w);
            }
        }
    }
    printf("%d\n", dp[n]);
    return 0;
}

P1507 NASA的食物计划

思路

• 这题有两个限制量（二维的01背包）

• 所以数组定义为：

• #define MAX_VW 405
  int dp[MAX_VW][MAX_VW];
  

• 由数据规模大小可以知道，可以来个二重循环求每个体积重量下的最大卡路里

代码演示

#include <stdio.h>
inline int read() {
    int x = 0, w = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar(); 
    }
    return w ? -x : x;
}
#define max(a, b) ((a) > (b) ? (a) : (b))

#define MAX_VW 405
int dp[MAX_VW][MAX_VW];
int n, V, W;
int main() {
    V = read(), W = read();
    n = read();
    for (int i = 1, v, w, k; i <= n; i++) {
        v = read(), w = read(), k = read();
        for (int j = V; j; j--) {
            if (j >= v) {
                for (int l = W; l; l--) {
                    if (l >= w) {
                        dp[j][l] = max(dp[j][l], dp[j - v][l - w] + k);
                    }
                }
            }
        }
    }
    printf("%d\n", dp[V][W]);
    
    return 0;
}

P1910 L国的战斗之间谍 题解

• 二维背包模板
• 自己了解一下

代码演示

#include <stdio.h>
inline int read() {
    int x = 0, w = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -x : x;
}

#define max(a, b) ({\
    (a) > (b) ? (a) : (b);\
})

int dp[1001][1001];

int main() {
    int n, m, x;
    n = read(), m = read(), x = read();
    for (int i = 1; i <= n; i++) {
        int a, b, c;
        a = read(), b = read(), c = read();
        for (int j = m; j >= b; j--) {
            for (int k = x; k >= c; k--) {
                dp[j][k] = max(dp[j][k], dp[j - b][k - c] + a);
            }
        }
    }
    printf("%d\n", dp[m][x]);
    return 0;
} 

P1832 A+B Problem（再升级）

思路

• 完全背包套用

• 对于每个素数数量没有限制，素数本身就是体积，素数个数就是价格

• 条件初始化：

• dp[0] = 1
  

• 转移方程

• dp[j] += dp[j - prime[i]];
  

P2563 [AHOI2001]质数和分解

思路

• 记得初始化条件

• dp[0] = 1;
  

代码演示

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

int n;
int prime[200];
inline void init() {
    for (int i = 2; i <= 200; i++) {
        if (!prime[i]) prime[++prime[0]] = i;
        for (int j = 1; j <= prime[0]; j++) {
            if (i * prime[j] > 200) break;
            prime[i * prime[j]] = 1;
            if (i % prime[j] == 0) break; 
        }
    }
//    for (int i = 0; i <= prime[0]; i++) printf("%d\n", prime[i]);
    return ;
}
long long dp[201];

int main() {
    init();
    dp[0] = 1;
    for (int i = 1; i <= prime[0]; i++) {
        for (int j = prime[i]; j <= 200; j++) {
            #define max(a, b) ((a) > (b) ? (a) : (b))
            dp[j] += dp[j - prime[i]];
        }
    }    
    while (scanf("%d", &n) != EOF) {
        printf("%lld\n", dp[n]);    
    }

    return 0;
}

P1679 神奇的四次方数

思路

代码演示

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <queue>
using namespace std;

#define min(a, b) ({\
    (a) < (b) ? (a) : (b);\
})
int dp[100005];
int power[20];
void init() {
    for (int i = 1; i < 19; i++) {
        power[i] = (int)pow(i, 4);
    }
    return ;
}

int main() {
    init();
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0; //初始化，最重要 
    int n;
    scanf("%d", &n);
    for (int i = 1; i < 19; i++) {
        for (int j = power[i]; j <= n; j++) {
            dp[j] = min(dp[j], dp[j - power[i]] + 1);
        }
    }
    printf("%d\n", dp[n]);
    return 0;
}

代码演示

#include <stdio.h>
#define MAX_N 1001
int prime[MAX_N];
inline void init() { //快速线性筛 
    for (int i = 2; i <= MAX_N; i++) {
        if (!prime[i]) prime[++prime[0]] = i;
        for (int j = 1; j <= prime[0]; j++) {
            if (i * prime[j] >= MAX_N) break;
            prime[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
    return ;
}
int n;
long long dp[MAX_N + 1];

int main() {
    init();
    //n = read();
    scanf("%d", &n);
    dp[0] = 1;
    for (int i = 1; prime[i] <= n; i++) { //小优化，提前结束循环 
        for (int j = prime[i]; j <= n; j++) { //小优化，减少使用if语句 
            dp[j] += dp[j - prime[i]];
        }
    }
    printf("%lld\n", dp[n]);
    return 0;
}

P1164 小A点菜

思路

• 跟上面那道题一样，都是求方案数量

• 那么0块钱点菜的方法也是一种方法，则初始化条件;

• dp[0] = 1;
  

• 由于每种菜只有一份，那么这是一道01背包问题

• 所以转移方程：

• dp[j] += dp[j - a];
  

代码演示

#include <stdio.h>
inline int read() {
    int x = 0, w = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar(); 
    }
    return w ? -x : x;
}

#define MAX_M 10000

int dp[MAX_M];
int n, m;

int main() {
    dp[0] = 1; // 条件初始化
    n = read(), m = read();
    for (int a, i = 1; i <= n; i++) {
        a = read();
        for (int j = m; j >= a; j--) {
            dp[j] += dp[j - a];  // 转移方程
        }
    }
    printf("%d\n", dp[m]);
    return 0;
}

P2722 [USACO3.1]总分 Score Inflation

思路

• 完全背包直接套用

代码演示

//完全背包

#include <stdio.h>
inline int read() {
    int x = 0, w = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar(); 
    }
    return w ? -x : x;
}
#define max(a, b) ((a) > (b) ? (a) : (b))

int n, m;
int dp[10000];

int main() {
    m = read(), n = read();
    for (int t, p, i = 1; i <= n; i++) {
        p = read(), t = read();
        for (int j = t; j <= m; j++) {
            dp[j] = max(dp[j], dp[j - t] + p);
        }
    }
    printf("%d\n", dp[m]);
    return 0; 
} 

P2925 [USACO08DEC]Hay For Sale S

思路

• 01背包

代码演示

#include <stdio.h>
inline int read() {
    int x = 0, w = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar(); 
    }
    return w ? -x : x;
}
int dp[50004];

int V, n;
#define max(a, b) ({\
    (a) > (b) ? (a) : (b);\
})


int main() {
    V = read(), n = read();
    for (int v, i = 1; i <= n; i++) {
        v = read();
        for (int j = V; j >= v; j--) {
            dp[j] = max(dp[j], dp[j - v] + v);
        }
        if (dp[V] == V) { //最多只能装V体积干草 
            printf("%d\n", V);
            return 0;
        }
    }
    printf("%d\n", dp[V]);
    return 0;
} 

P1757 通天之分组背包

思路

• 看注释
• 01背包

代码演示

#include <stdio.h>
#include <vector>
using namespace std;

inline int read() {
    int x = 0, w = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar(); 
    }
    return w ? -x : x;
}

#define max(a, b) ({\
    (a) > (b) ? (a) : (b);\
})
#define MAX_N 1001
struct Node {
    int a, b;
};
vector <vector <Node> > num(MAX_N, vector<Node>()); // 建立邻接表 

int dp[MAX_N];

int main() {
    int n, m;
    m = read(), n = read();
    for (int i = 1; i <= n; i++) {
        int a, b, c;
        a = read(), b = read(), c = read();
        num[c].push_back((Node){a, b});
    }
    for (int i = 1; i < MAX_N; i++) { // 遍历所有组 
        if ((int)num.size() == 0) continue;
        /* 注意第二重与第三重循环顺序不能反， 
           顺序反了不能保证每组物品只放有一个；
           该顺序可以保证在体积为j的情况下，
           遍历该组所有物品，更新得到最大价值
        */
        for (int j = m; j; j--) { 
            for (int k = 0; k < (int)num[i].size(); k++) { //遍历该组所有物品 
                if (j >= num[i][k].a) dp[j] = max(dp[j], dp[j - num[i][k].a] + num[i][k].b);
            }
        }
    }
    printf("%d\n", dp[m]);
    return 0;
} 

P1616 疯狂的采药

思路

• 多重背包

代码演示

#include <stdio.h>
inline int read() {
    int x = 0, w = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar(); 
    }
    return w ? -x : x;
}

#define max(a, b) ({\
    (a) > (b) ? (a) : (b);\
})

#define MAX_T 10000007

long long dp[MAX_T];


int main() {
    int t, m;
    t = read(), m = read();
    for (int i = 1; i <= m; i++) {
        int a, b;
        a = read(), b = read();
        for (int j = a; j <= t; j++) {
            dp[j] = max(dp[j], dp[j - a] + b);
        }
    }
    printf("%lld\n", dp[t]);
    return 0;
} 

P2871 [USACO07DEC]Charm Bracelet S

思路

• 01背包

代码演示

#include <stdio.h>
inline int read() {
    int x = 0, w = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -x : x;
}

#define max(a, b) ({\
    (a) > (b) ? (a) : (b);\
})

int dp[100004];

int V, n;
int main() {
    n = read(), V = read();
    for (int v, w, i = 1; i <= n; i++) {
        v = read(), w = read();
        for (int j = V; j >= v; j--) {
            dp[j] = max(dp[j], dp[j - v] + w);
        }
    }
    printf("%d\n", dp[V]);
    return 0;
} 

P2392 kkksc03考前临时抱佛脚

思路

• 首选01背包

• 左右大脑同时计算，仅限于同一科，那么可以初始化4个01背包数组

• dp[4][5000];
  

• 对于题目要求时间最少，那么对于左右大脑，这两个大脑消耗的时间尽可能趋近于该科目消耗的时间总和sum的一半

• 那么我们可以计算当背包容量为sum >> 1时，所装入的最大价值（消耗时间），其中

• dp[i][sum >> 1] <= sum - dp[i][sum];
  i为第几科目
  

• 那么转移方程为：

• dp[i][j] = max(dp[i][j], dp[i][j - s] + s);
  

代码演示

#include <stdio.h>
#include <algorithm>
using namespace std;

inline int read() {
    int x = 0, w = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -x : x;
}

#define max(a, b) ({\
    (a) > (b) ? (a) : (b);\
})

int s[4][21];
int dp[4][5000]; //四个科目相互独立。所以利用四个01背包 
int ans;

int main() {
    int S[4];
    for (int i = 0; i < 4; i++) {
        S[i] = read(); 
    }
    for (int i = 0; i < 4; i++) {
        int sum = 0;
        for (int j = 1; j <= S[i]; j++) {
            s[i][j] = read();
            sum += s[i][j];
        }
        for (int k = 1; k <= S[i]; k++) {
            for (int j = sum >> 1; j >= s[i][k]; j--) {
                dp[i][j] = max(dp[i][j], dp[i][j - s[i][k]] + s[i][k]);
            }
        }
        ans += sum - dp[i][sum >> 1]; // dp[i][sum >> 1] <= sum - dp[i][sum >> 1]
    }
    printf("%d\n", ans);
    return 0;
}

P1855 榨取kkksc03

思路

• 二维背包，自己看上面的题目

代码演示

#include <stdio.h>
inline int read() {
    int x = 0, w = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -x : x;
}

#define max(a, b) ({\
    (a) > (b) ? (a) : (b);\
})
int dp[205][205];

int main() {
    int n, M, T;
    n = read(), M = read(), T = read();
    for (int i = 1; i <= n; i++) {
        int m, t;
        m = read(), t = read();
        for (int tt = T; tt >= t; tt--) {
            for (int mm = M; mm >= m; mm--) {
                dp[tt][mm] = max(dp[tt][mm], dp[tt - t][mm - m] + 1);
            }
        }
    }
    printf("%d\n", dp[T][M]);
    
    return 0;
} 

P1510 精卫填海

思路

• 01背包

代码演示

#include <stdio.h>
inline int read() {
    int x = 0, w = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -x : x;
}

#define max(a, b) ({\
    (a) > (b) ? (a) : (b);\
})
int dp[10005];

int main() {
    int v, n, c;
    v = read(), n = read(), c = read();
    for (int i = 1, k, m; i <= n; i++) {
        k = read(), m = read();
        for (int j = c; j >= m; j--) {
            dp[j] = max(dp[j], dp[j - m] + k);
        }
    }
    for (int j = 1; j <= c; j++) { //得出全部答案遍历答案得出最大值
        if (dp[j] >= v) {
            printf("%d\n", c - j);
            return 0;
        }
    }
    printf("Impossible\n");    
    return 0;
}

P1877 [HAOI2012]音量调节

思路

• 不能进行空间优化的01背包，至少我目前不会，看代码
• 对于每一首歌，在那个音量的范围内，我们可以利用前一首歌改变的音量标记当前这首歌能达到的音量
• 最后从大到小遍历标记过的音量，进行输出，如果没有标记则输出-1

代码演示

#include <stdio.h>
inline int read() {
    int x = 0, w = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -x : x;
}

#define max(a, b) ({\
    (a) > (b) ? (a) : (b);\
})

int dp[51][1004];

int main() {
    int n, bl, ml;
    n = read(), bl = read(), ml = read();
    dp[0][bl] = 1;
    for (int a, i = 1; i <= n; i++) {
        a = read();
        for (int j = 0; j <= ml; j++) {
            if (dp[i - 1][j]) {
                if (j >= a) dp[i][j - a] = 1;
                if (j + a <= ml) dp[i][j + a] = 1;
            }
        }
    }
    for (int i = ml; i >= 0; i--) {
        if (dp[n][i]) {
            printf("%d\n", i);
            return 0;
        }
    }
    printf("-1");
    return 0;
}