[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 h 和质量最大值 t t t。
第二行 1 1 1 个整数代表食品总数 n n n。
接下来 n n n 行每行 3 3 3 个数 体积 h i h_i hi，质量 t i t_i ti，所含卡路里 k i k_i ki。
输出格式
一个数，表示所能达到的最大卡路里（int 范围内）
样例 #1
样例输入 #1
320 350
4
160 40 120
80 110 240
220 70 310
40 400 220
样例输出 #1
550
提示
对于 100 % 100\% 100% 的数据， h , t , h i , t i ≤ 400 h,t,h_i,t_i \le 400 h,t,hi,ti≤400， n ≤ 50 n \le 50 n≤50， k i ≤ 500 k_i \le 500 ki≤500。
代码
#include <stdio.h>
int max(int a, int b);
#define MAX 1000
int 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;
}
}
