C语言-算法-背包

时间：2024-01-27 20:40:22

[USACO07DEC] Charm Bracelet S（01背包）

题目描述

Bessie has gone to the mall’s jewelry store and spies a charm bracelet. Of course, she’d like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight Wi (1 ≤ Wi ≤ 400), a ‘desirability’ factor Di (1 ≤ Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).

Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.

有 N N N 件物品和一个容量为 M M M 的背包。第 i i i 件物品的重量是 W i W_i Wi​，价值是 D i D_i Di​。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入格式

* Line 1: Two space-separated integers: N and M

* Lines 2…N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di

第一行：物品个数 N N N 和背包大小 M M M。

第二行至第 N + 1 N+1 N+1 行：第 i i i 个物品的重量 W i W_i Wi​ 和价值 D i D_i Di​。

输出格式

* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints

输出一行最大价值。

样例 #1

样例输入 #1

4 6
1 4
2 6
3 12
2 7

样例输出 #1

23

代码实现

#include <stdio.h>
int max(int a, int b); // 用于判断两个数的大小的函数
#define MAX 30000
int N, M;
int W[MAX], D[MAX];
int dp[MAX]; // dp[j]表示总重量不超过j时的最大价值

int main()
{
    int i, j;
    scanf("%d %d", &N, &M);

    for (i = 1; i <= N; i++)
    {
        scanf("%d %d", &W[i], &D[i]);
    }
    for (i = 1; i <= N; i++) // 用动态规划来计算最大值
    {
         // 如果当前物品可以放入背包，那么尝试放入，并更新dp数组
        for (j = M; j >= W[i]; j--)
        {
            dp[j] = max(dp[j], dp[j - W[i]] + D[i]);
        }
    }
    printf("%d\n", dp[M]); // 输出背包能装入的最大价值
    return 0;
}

int max(int a, int b) // 用于判断两个数的大小的函数
{
    if (a > b)
    {
        return a;
    }
    else
    {
        return b;
    }
}

A - Bone Collector

题目描述

许多年前，在泰迪的家乡，有一个被称为“骨头收集者”的人。这个人喜欢收集各种骨头，比如狗的、牛的，甚至还去过坟墓……
骨头收集者有一个容积为V的大袋子，在他收集的过程中有很多骨头，显然，不同的骨头有不同的价值和不同的体积，现在给出每个骨头的价值，请你计算出骨头收集者能够获得的最大总价值？

输入

第一行包含一个整数T，表示案例的数量。
接下来是T个案例，每个案例包括三行，第一行包含两个整数N，V，(N <= 1000, V <= 1000)，表示骨头的数量和他的袋子的容积。第二行包含N个整数，表示每个骨头的价值。第三行包含N个整数，表示每个骨头的体积。

输出

每行输出一个整数，表示最大的总价值（这个数字将小于231）。

样例

Input

在这里插入图片描述

Output

在这里插入图片描述

代码

#include <stdio.h>
int max(int a, int b);
#define MAX 2000

int main()
{
    int T, N, V, i, j, k;
    int D[MAX], v[MAX], dp[MAX];
    scanf("%d", &T); // 数量

    for (i = 1; i <= T; i++)
    {
        scanf("%d %d", &N, &V); // 数量和袋子的容积
        for (j = 1; j <= N; j++)
        {
            scanf("%d", &D[j]); // 价值
        }
        for (k = 1; k <= N; k++)
        {
            scanf("%d", &v[k]); // 体积
        }
        for (i = 0; i <= V; i++)
        {
            dp[i] = 0; // 初始化dp数组
        }
        for (i = 1; i <= N; i++)
        {
            for (j = V; j >= v[i]; j--)
            {
                dp[j] = max(dp[j], dp[j - v[i]] + D[i]);
            }
        }
        printf("%d\n", dp[V]);
    }
    return 0;
}

int max(int a, int b)
{
    if (a > b)
    {
        return a;
    }
    else
    {
        return b;
    }
}

[NOIP2006 普及组] 开心的金明（01背包）

题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 N N N 元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 N N N 元。于是，他把每件物品规定了一个重要度，分为 5 5 5 等：用整数 1 − 5 1-5 1−5 表示，第 5 5 5 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过 N N N 元（可以等于 N N N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第 j j j件物品的价格为 v j v_j vj​，重要度为 w j w_j wj​，共选中了 k k k 件物品，编号依次为 j 1 , j 2 , … , j k j_1,j_2,…,j_k j1​,j2​,…,jk​，则所求的总和为：

v j 1 × w j 1 + v j 2 × w j 2 … + v j k × w j k v_{j_1} \times w_{j_1}+v_{j_2} \times w_{j_2} …+v_{j_k} \times w_{j_k} vj1​​×wj1​​+vj2​​×wj2​​…+vjk​​×wjk​​。

请你帮助金明设计一个满足要求的购物单。

输入格式

第一行，为 2 2 2 个正整数，用一个空格隔开： n , m n,m n,m（ n < 30000 , m < 25 n<30000,m<25 n<30000,m<25）其中 n n n 表示总钱数， m m m 为希望购买物品的个数。

从第 2 2 2 行到第 m + 1 m+1 m+1 行，第 j j j 行给出了编号为 j − 1 j-1 j−1 的物品的基本数据，每行有 2 2 2 个非负整数 v , p v,p v,p（其中 v v v 表示该物品的价格 ( v ≤ 10000 ) (v \le 10000) (v≤10000)， p p p 表示该物品的重要度（ 1 ≤ p ≤ 5 1\le p\le5 1≤p≤5）。

输出格式

1 1 1 个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（ < 100000000 <100000000 <100000000）。

样例 #1

样例输入 #1

1000 5
800 2
400 5
300 5
400 3
200 2

样例输出 #1

3900

代码

#include <stdio.h>
#include <string.h>
int max(int a, int b);
#define MAX 40000

int main()
{
    int n, m, i, j, v[MAX], p[MAX], a[MAX]; // 数组a表示每种物品的价格和重要度乘积
    long long dp[MAX];
    memset(dp, 0, sizeof(dp)); // 初始化，dp表示不超过总钱数的物品的价格与重要度乘积的总和的最大值
    scanf("%d %d", &n, &m); // 总钱数和希望购买物品的个数

    for (i = 1; i <= m; i++)
    {
        scanf("%d %d", &v[i], &p[i]); // 物品的价格和重要程度
        a[i] = v[i] * p[i];
    }
    for (i = 1; i <= m; i++)
    {
        for (j = n; j >= v[i]; j--)
        {
            dp[j] = max(dp[j], dp[j - v[i]] + a[i]);
        }
    }
    printf("%lld", dp[n]);
    return 0;
}

int max(int a, int b)
{
    if (a > b)
    {
        return a;
    }
    else
    {
        return b;
    }
}

NASA的食物计划（二维费用背包）

题目背景

NASA（美国航空航天局）因为航天飞机的隔热瓦等其他安全技术问题一直大伤脑筋，因此在各方压力下终止了航天飞机的历史，但是此类事情会不会在以后发生，谁也无法保证。所以，在遇到这类航天问题时，也许只能让航天员出仓维修。但是过多的维修会消耗航天员大量的能量，因此 NASA 便想设计一种食品方案，使体积和承重有限的条件下多装载一些高卡路里的食物。

题目描述

航天飞机的体积有限，当然如果载过重的物品，燃料会浪费很多钱，每件食品都有各自的体积、质量以及所含卡路里。在告诉你体积和质量的最大值的情况下，请输出能达到的食品方案所含卡路里的最大值，当然每个食品只能使用一次。

输入格式

第一行 2 2 2 个整数，分别代表体积最大值 h h

相关文章