首页 > 试题广场 >

【模板】完全背包

[编程题]【模板】完全背包
  • 热度指数：13173 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
你有一个背包，最多能容纳的体积是V。

现在有n种物品，每种物品有任意多个，第i种物品的体积为v_i ,价值为w_i。

（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？

输入描述:
第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个数v_i和w_i，表示第i种物品的体积和价值。




输出描述:
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。
示例1

输入

2 6
5 10
3 1

输出

10
2
示例2

输入

3 8
3 10
9 1
10 1

输出

20
0

说明

无法恰好装满背包。
示例3

输入

6 13
13 189
17 360
19 870
14 184
6 298
16 242

输出

596
189

说明

可以装5号物品2个，达到最大价值298*2=596，若要求恰好装满，只能装1个1号物品，价值为189.
算法知识视频讲解
添加回答
C
靖意风头像 靖意风
1. 使用dp表进行分析, 理解dp表的含义。mem[ix][jx] 表示 包容量是jx时候，装下ix个物品时，表示的最大价值

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX(x, y) ((x) > (y) ? (x) : (y))


int get_dp_value(int** mem, int cnt, int tgt, int* w, int* v) {

    for (int ix = 1; ix <= cnt; ix++) {
        for (int jx = 1; jx <= tgt; jx++) {
            if (jx < w[ix])
                mem[ix][jx] = mem[ix-1][jx];
            else
                mem[ix][jx] = MAX(mem[ix-1][jx], v[ix]+mem[ix][jx - w[ix]]);
        }
    }
    return mem[cnt][tgt];
}

int main() {
    int cnt = 0, tgt = 0, val = 0;
    scanf("%d %d", &cnt, &tgt);
    int w[cnt+1], v[cnt+1];
    for (int ix = 1; ix <= cnt; ix++)
        scanf("%d %d", &w[ix], &v[ix]);

    int **mem = malloc((cnt + 1) * sizeof(*mem));
    for (int ix = 0; ix <= cnt; ix++) {
        mem[ix] = malloc((tgt + 1) * sizeof(int));
    }
    // 设置初值
    memset(mem[0], 0, sizeof(int) * (tgt + 1));
    for (int ix = 1; ix <= cnt; ix++)
        mem[ix][0] = 0;

    val = get_dp_value(mem, cnt, tgt, w, v);
    printf("%d\n",  val);

    // 设置初值
    for (int ix = 0; ix <= cnt; ix++)
        mem[ix][0] = 0;
    for (int ix = 1; ix <= tgt; ix++)
        mem[0][ix] = INT_MIN;

    val = get_dp_value(mem, cnt, tgt, w, v);
    printf("%d\n",  val < 0 ? 0 : val);
    return 0;
}

2. 将dp 表进行简化
#include <stdio.h>
#include <limits.h>

#define MAX(x, y) ((x) > (y) ? (x) : (y))
int get_dp_value(int* mem, int cnt, int tgt, int* w, int* v) {

    for (int ix = 1; ix <= cnt; ix++)
        for (int jx = w[ix]; jx <= tgt; jx++)
            mem[jx] = MAX(mem[jx], v[ix] + mem[jx - w[ix]]);

    return mem[tgt];
}

int main() {
    int cnt = 0, tgt = 0, val = 0;
    scanf("%d %d", &cnt, &tgt);
    int w[cnt+1], v[cnt+1];
    for (int ix = 1; ix <= cnt; ix++)
        scanf("%d %d", &w[ix], &v[ix]);

    int mem[tgt + 1];
    memset(mem, 0, sizeof(int) * (tgt + 1));
    val = get_dp_value(mem, cnt, tgt, w, v);
    printf("%d\n",  val);

    for (int ix = 1; ix <= tgt; ix++)
        mem[ix] = INT_MIN;
    mem[0] = 0;
    val = get_dp_value(mem, cnt, tgt, w, v);
    printf("%d\n",  val < 0 ? 0 : val);
    return 0;
}


发表于 2025-01-20 02:11:35 回复(0)
C
cs小白_头像 cs小白_ 
#include <stdio.h>
#include <limits.h>
int max(int a, int b) {
    return (a > b ? a : b);
}
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int v[n + 1], w[n + 1], dp[n + 1][m + 1];
    v[0] = 0, w[0] = 0;
    for (int i = 0; i <= m; i++) {
        dp[0][i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        dp[i][0] = 0;
        scanf("%d %d", &v[i], &w[i]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j<v[i]) {
                   dp[i][j]=dp[i - 1][j];
            }
            else {
                dp[i][j] = max(dp[i - 1][j],dp[i][j-v[i]]+w[i]);
            }
            }

        }
    
    printf("%d\n", dp[n][m]);
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }
    for (int i = 1; i <= m; i++) {
        dp[0][i] = INT_MIN;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j<v[i]) {
                   dp[i][j]=dp[i - 1][j];
            }
            else {
                dp[i][j] = max(dp[i - 1][j],dp[i][j-v[i]]+w[i]);
            }
           
        }
    }
    printf("%d", (dp[n][m] > 0 ? dp[n][m] : 0));

    return 0;
}

发表于 2024-12-01 11:50:16 回复(0)
提交观点

问题信息

难度：
2条回答 1478浏览

热门推荐

通过挑战的用户

查看代码

相关试题

【模板】完全背包

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号