C语言-算法-背包

[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$ 件物品和一个容量为 $M$ 的背包。第 $i$ 件物品的重量是 Wi W_iWi​，价值是 Di D_iDi​。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入格式

* 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$ 和背包大小 $M$。

第二行至第 $N+1$ 行：第 $i$ 个物品的重量 Wi W_iWi​ 和价值 Di D_iDi​。

输出格式

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

输出一行最大价值。

样例 #1

样例输入 #1

4 61 42 63 122 7

样例输出 #1

23

代码实现

#include int max(int a, int b); // 用于判断两个数的大小的函数#define MAX 30000int 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 int max(int a, int b);#define MAX 2000int 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$ 元。于是，他把每件物品规定了一个重要度，分为 $5$ 等：用整数 $1-5$ 表示，第 $5$ 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过 $N$ 元（可以等于 $N$ 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第$j$件物品的价格为 vj v_jvj​，重要度为 wj w_jwj​，共选中了 $k$ 件物品，编号依次为 j1, j2, … , jk j_1,j_2,…,j_kj1​,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$ 个正整数，用一个空格隔开：$n,m$（$n<30000,m<25$）其中 $n$ 表示总钱数，$m$ 为希望购买物品的个数。

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

输出格式

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

样例 #1

样例输入 #1

1000 5800 2400 5300 5400 3200 2

样例输出 #1

3900

代码

#include #include int max(int a, int b);#define MAX 40000int 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$ 个整数，分别代表体积最大值 $h$ 和质量最大值 $t$。

第二行 $1$ 个整数代表食品总数 $n$。

接下来 $n$ 行每行 $3$ 个数 体积 hi h_ihi​，质量 ti t_iti​，所含卡路里 ki k_iki​。

输出格式

一个数，表示所能达到的最大卡路里（int 范围内）

样例 #1

样例输入 #1

320 3504160 40 12080 110 240220 70 31040 400 220

样例输出 #1

550

提示

对于 $100\%$ 的数据， h , t , hi, ti≤ 400h,t,h_i,t_i \le 400h,t,hi​,ti​≤400，$n\le 50$， ki≤ 500k_i \le 500ki​≤500。

代码

#include int max(int a, int b);#define MAX 1000int dp[MAX][MAX];int main(){int h, t, n, i, j, k;int H[MAX], T[MAX], K[MAX];scanf("%d %d", &h, &t); // 体积最大值和质量最大值scanf("%d", &n); // 食品总数for (i = 1; i <= n; i++){scanf("%d %d %d", &H[i], &T[i], &K[i]); // 体积，质量，卡路里}for (i = 1; i <= n; i++) // 动态规划{for (j = h; j >= H[i]; j--){for (k = t; k >= T[i]; k--){dp[j][k] = max(dp[j][k], dp[j - H[i]][k - T[i]] + K[i]);}}}printf("%d\n", dp[h][t]);return 0;}int max(int a, int b){if (a > b){return a;}else{return b;}}