描述
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。 输出最大价值。
输入格式 第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。
输出格式 输出一个整数,表示最大价值。
数据范围 0<N,V≤1000 0<vi,wi≤1000
4 5
1 2
2 4
3 4
4 5
输出样例:
输出样例:
8
思想
dp[i][j]
表示前i
个物品,总体积不超过j
的价值i
个 物品:dp[i][j] = dp[i - 1][j]
i
个物品:dp[i][j] = dp[i - 1][j - v[i]] + w[i]
max()
j < v[i]
时,不能选择物品,反之可选代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int dp[N][N];
int v[N], w[N];
void solve(){
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i ++){
for(int j = 0; j <= m; j ++){
dp[i][j] = dp[i - 1][j]; //不选物品i
if(j >= v[i]) dp[i][j] = max(dp[i][j],dp[i - 1][j - v[i]] + w[i]); //选择物品i
}
}
cout << dp[n][m] << endl;
}
int main(){
solve();
return 0;
}
优化
dp[i][j]
记录了全部的i
个物品在j
容量下的最大价值,但我们只需要dp[n][m]
,故只需要dp[j]
dp[i][j]
的更新,dp[i][j] = max(dp[i][j],dp[i - 1][j - v[i]] + w[i])
,当第一维的i
被省略后,更新时会产生歧义dp[j]
需要从j = m
到j = v[i]
逆序,避免歧义dp[j] = max(dp[j],dp[j - v[i]] + w[i])
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int dp[N];
int v[N], w[N];
void solve(){
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i ++){
for(int j = m; j >= v[i]; j --){
dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
}
}
cout << dp[m] << endl;
}
int main(){
solve();
return 0;
}
描述
金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。
更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过 N 元钱就行”。
今天一早金明就开始做预算,但是他想买的东西太多了,肯定会超过妈妈限定的 N 元。
于是,他把每件物品规定了一个重要度,分为 5 等:用整数 1∼5 表示,第 5 等最重要。
他还从因特网上查到了每件物品的价格(都是整数元)。
他希望在不超过 N 元(可以等于 N 元)的前提下,使每件物品的价格与重要度的乘积的总和最大。
设第 j 件物品的价格为 v[j],重要度为 w[j],共选中了 k 件物品,编号依次为 j1,j2,…,jk,则所求的总和为:
v[j1]×w[j1]+v[j2]×w[j2]+…+v[jk]×w[jk] 请你帮助金明设计一个满足要求的购物单。
输入格式 输入文件的第 1 行,为两个正整数 N 和 m,用一个空格隔开。(其中 N 表示总钱数,m 为希望购买物品的个数)
从第 2 行到第 m+1 行,第 j 行给出了编号为 j−1 的物品的基本数据,每行有 2 个非负整数 v 和 p。(其中 v 表示该物品的价格,p 表示该物品的重要度)
输出格式 输出文件只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(数据保证结果不超过 108)。
数据范围 1≤N<30000, 1≤m<25, 0≤v≤10000, 1≤p≤5 输入样例:
1000 5
800 2
400 5
300 5
400 3
200 2
输出样例:
3900
思想
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int dp[N];
int v[N], w[N];
void solve(){
int n, m;
cin >> m >> n;
for(int i = 1; i <= n; i ++){
cin >> v[i] >> w[i];
w[i] *= v[i];
}
for(int i = 1; i <= n; i ++){
for(int j = m; j >= v[i]; j --){
dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
}
}
cout << dp[m] << endl;
}
int main(){
solve();
return 0;
}
描述
有一个箱子容量为 V,同时有 n 个物品,每个物品有一个体积(正整数)。
要求 n 个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。
输入格式 第一行是一个整数 V,表示箱子容量。
第二行是一个整数 n,表示物品数。
接下来 n 行,每行一个正整数(不超过10000),分别表示这 n 个物品的各自体积。
输出格式 一个整数,表示箱子剩余空间。
数据范围 0<V≤20000, 0<n≤30 输入样例:
24
6
8
3
12
7
9
7
输出样例:
0
思想
dp[j]
表示体积不超过j
时,已使用的体积dp[j] = max(dp[j],dp[j - v[i]] + v[i])
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int dp[N];
int v[N];
void solve(){
int n, m;
cin >> m >> n;
for(int i = 1; i <= n; i ++) cin >> v[i];
for(int i = 1; i <= n; i ++){
for(int j = m; j >= v[i]; j --){
dp[j] = max(dp[j],dp[j - v[i]] + v[i]);
}
}
cout << m - dp[m] << endl;
}
int main(){
solve();
return 0;
}
描述
给定 N 个正整数 A1,A2,…,AN,从中选出若干个数,使它们的和为 M,求有多少种选择方案。
输入格式 第一行包含两个整数 N 和 M。
第二行包含 N 个整数,表示 A1,A2,…,AN。
输出格式 包含一个整数,表示可选方案数。
数据范围 1≤N≤100, 1≤M≤10000, 1≤Ai≤1000, 答案保证在 int 范围内。
输入样例:
4 4
1 1 2 2
输出样例:
3
思想
dp[i][j]
表示前i
个数选择的数之和恰好等于j
的集合i
个数:dp[i][j] = dp[i][j]
i
个数:dp[i][j] = dp[i - 1][j - v[i]]
dp[0][0] = 1
,j = 0
时不选即为一种方案dp[i][j] += dp[i - 1][j - v[i]]
dp[j] += dp[j - v[i]]
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 3;
int dp[N];
int v[N];
void solve(){
int n, m;
cin >> n >> m;
dp[0] = 1;
for(int i = 1; i <= n; i ++){
cin >> v[i];
}
for(int i = 1; i <= n; i ++){
for(int j = m; j >= v[i]; j --){
dp[j] += dp[j - v[i]];
}
}
cout << dp[m] << endl;
}
int main(){
solve();
return 0;
}
描述
岩石怪物杜达生活在魔法森林中,他在午餐时收集了 N 块能量石准备开吃。
由于他的嘴很小,所以一次只能吃一块能量石。
能量石很硬,吃完需要花不少时间。
吃完第 i 块能量石需要花费的时间为 Si 秒。
杜达靠吃能量石来获取能量。
不同的能量石包含的能量可能不同。
此外,能量石会随着时间流逝逐渐失去能量。
第 i 块能量石最初包含 Ei 单位的能量,并且每秒将失去 Li 单位的能量。
当杜达开始吃一块能量石时,他就会立即获得该能量石所含的全部能量(无论实际吃完该石头需要多少时间)。
能量石中包含的能量最多降低至 0。
请问杜达通过吃能量石可以获得的最大能量是多少?
输入格式 第一行包含整数 T,表示共有 T 组测试数据。
每组数据第一行包含整数 N,表示能量石的数量。
接下来 N 行,每行包含三个整数 Si,Ei,Li。
输出格式 每组数据输出一个结果,每个结果占一行。
结果表示为 Case #x: y,其中 x 是组别编号(从 1 开始),y 是可以获得的最大能量值。
数据范围 1≤T≤10, 1≤N≤100, 1≤Si≤100, 1≤Ei≤105, 0≤Li≤105 输入样例:
3
4
20 10 1
5 30 5
100 30 1
5 80 60
3
10 4 1000
10 3 1000
10 8 1000
2
12 300 50
5 200 0
输出样例:
Case #1: 105
Case #2: 8
Case #3: 500
思想
代码
#include <bits/stdc++.h>
using namespace std;
int _, __;
const int N = 110;
struct point{
int s, e, l;
bool operator < (const point &p) const{
return s * p.l < p.s * l;
}
};
void solve(){
int dp[N * N] = {0};
point p[N];
int n;
cin >> n;
int m = 0;
for(int i = 1; i <= n; i++) {
cin >> p[i].s >> p[i].e >> p[i].l;
m += p[i].s;
}
sort(p + 1, p + 1 + n);
for(int i = 1; i <= n; i++) {
for(int j = m; j >= p[i].s; j--){
dp[j] = max(dp[j], dp[j - p[i].s] + max(0, p[i].e - (j - p[i].s) * p[i].l));
}
}
int res = 0;
for(int i = 1; i <= m; i++) res = max(res, dp[i]);
printf("Case #%d: %d\n", __, res);
}
int main(){
int _;
cin >> _;
for(__ = 1; __ <= _; __ ++){
solve();
}
return 0;
}
描述
有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。
第 i 种物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。 输出最大价值。
输入格式 第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 种物品的体积和价值。
输出格式 输出一个整数,表示最大价值。
数据范围 0<N,V≤1000 0<vi,wi≤1000
4 5
1 2
2 4
3 4
4 5
输出样例:
输出样例:
10
思想
dp[i][j]
表示前i
个物品,总体积不超过j
的价值i
个 物品:dp[i][j] = dp[i - 1][j]
i
个物品共k
个:dp[i][j] = dp[i - 1][j - k * v[i]] + k * w[i]
max()
j < k * v[i]
时,不能选择物品,反之可选代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 +3;
int dp[N][N];
int v[N], w[N];
void solve(){
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i ++){
for(int j = 0; j <= m; j ++){
for(int k = 0; k * v[i] <= j; k ++){
dp[i][j] = max(dp[i][j],dp[i - 1][j - k * v[i]] + k * w[i]);
}
}
}
cout << dp[n][m] << endl;
}
int main(){
solve();
return 0;
}
优化
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i], dp[i - 1][j - 2 * v[i]] + 2 * w[i], dp[i - 1][j - 3 * v[i]] + 3 * w[i], ...)
dp[i][j - v[i]] = max(dp[i - 1][j - v[i]], dp[i - 1][j - 2 * v[i]] + w[i], dp[i - 1][j - 3 * v[i]] + 2 * w[i], ...)
dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])
,与k
取值无关k
层循环可以被优化掉dp[i][j] = max(dp[i][j],dp[i - 1][j - v[i]] + w[i])
dp[i][j] = max(dp[i][j],dp[i][j - v[i]] + w[i])
dp[i][j]
的第一维按01背包的思想将其优化:dp[j] = max(dp[j],dp[j - v[i]] + w[i])
i
不会产生歧义,故不需要逆序更新,顺序更新即可代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int dp[N];
int v[N], w[N];
void solve(){
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i ++){
for(int j = v[i]; j <= m; j ++){
dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
}
}
cout << dp[m] << endl;
}
int main(){
solve();
return 0;
}
描述
小明手里有n元钱全部用来买书,书的价格为10元,20元,50元,100元。
问小明有多少种买书方案?(每种书可购买多本)
输入格式 一个整数 n,代表总共钱数。
输出格式 一个整数,代表选择方案种数。
数据范围 0≤n≤1000
20
输出样例:
输出样例:
2
思想
dp[i][j]
表示前i
种书,选择的价格恰好等于j
的集合i
种书:dp[i][j] = dp[i - 1][j]
i
种书共k
本:dp[i][j] = dp[i - 1][j - k * v[i]]
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - k * v[i]]
j < k * v[i]
时,不能选择书,反之可选
dp[j] += dp[j - v[i]]
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int dp[N];
int v[N] = {0, 10, 20, 50, 100};
void solve(){
int m;
cin >> m;
dp[0] = 1;
for(int i = 1; i <= 4; i ++){
for(int j = v[i]; j <= m; j ++){
dp[j] += dp[j - v[i]];
}
}
cout << dp[m] << endl;
}
int main(){
solve();
return 0;
}
描述
给你一个n种面值的货币系统,求组成面值为m的货币有多少种方案。
输入格式 第一行,包含两个整数n和m。
接下来n行,每行包含一个整数,表示一种货币的面值。
输出格式 共一行,包含一个整数,表示方案数。
数据范围 n≤15,m≤3000 输入样例:
3 10
1
2
5
输出样例:
10
思想
dp[i][j]
表示前i
种货币,选择的面值恰好等于j
的集合i
种货币:dp[i][j] = dp[i - 1][j]
i
种货币共k
个:dp[i][j] = dp[i - 1][j - k * v[i]]
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - k * v[i]]
j < k * v[i]
时,不能选择货币,反之可选
dp[j] += dp[j - v[i]]
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N = 1e6 + 3;
LL dp[N];
LL v[N];
void solve(){
LL n, m;
cin >> n >> m;
dp[0] = 1;
for(LL i = 1; i <= n; i ++) cin >> v[i];
for(LL i = 1; i <= n; i ++){
for(LL j = v[i]; j <= m; j ++){
dp[j] += dp[j - v[i]];
}
}
cout << dp[m] << endl;
}
int main(){
solve();
return 0;
}
描述
有 n 种不同面额的货币,第 i 种货币的面额为 a[i],你可以假设每一种货币都有无穷多张。
为了方便,我们把货币种数为 n、面额数组为 a[1..n] 的货币系统记作 (n,a)。
在一个完善的货币系统中,每一个非负整数的金额 x 都应该可以被表示出,即对每一个非负整数 x,都存在 n 个非负整数 t[i] 满足 a[i]×t[i] 的和为 x。
然而,在网友的国度中,货币系统可能是不完善的,即可能存在金额 x 不能被该货币系统表示出。
例如在货币系统 n=3, a=[2,5,9] 中,金额 1,3 就无法被表示出来。
两个货币系统 (n,a) 和 (m,b) 是等价的,当且仅当对于任意非负整数 x,它要么均可以被两个货币系统表出,要么不能被其中任何一个表出。
现在网友们打算简化一下货币系统。
他们希望找到一个货币系统 (m,b),满足 (m,b) 与原来的货币系统 (n,a) 等价,且 m 尽可能的小。
他们希望你来协助完成这个艰巨的任务:找到最小的 m。
输入格式 输入文件的第一行包含一个整数 T,表示数据的组数。
接下来按照如下格式分别给出 T 组数据。
每组数据的第一行包含一个正整数 n。
接下来一行包含 n 个由空格隔开的正整数 a[i]。
输出格式 输出文件共有 T 行,对于每组数据,输出一行一个正整数,表示所有与 (n,a) 等价的货币系统 (m,b) 中,最小的 m。
数据范围 1≤n≤100, 1≤a[i]≤25000, 1≤T≤20 输入样例:
2
4
3 19 10 6
5
11 29 13 19 17
输出样例:
2
5
思想
dp[i][j]
表示前i
个数,数值为j
的方案vis[N]
记录出现过的方案数,cnt
记录选择的最小数量dp[i,vis[i]] == 0
说明该方案未曾出现,则cnt ++
dp[i][j] = dp[i - 1][j]
dp[i][j] = dp[i][j - vis[i]]
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - vis[i]]
dp[j] += dp[j - vis[i]]
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 3;
int vis[N];
bool dp[N];
void solve(){
memset(dp, 0, sizeof dp);
int n;
cin >> n;
for(int i = 0; i < n; i ++) cin >> vis[i];
sort(vis, vis + n);
int maxn = vis[n - 1];
int cnt = 0;
dp[0] = 1;
for(int i = 0; i < n; i ++){
if(!dp[vis[i]]) cnt ++;
for(int j = vis[i]; j <= maxn; j ++){
dp[j] += dp[j - vis[i]];
}
}
cout << cnt << endl;
}
int main(){
int _;
cin >> _;
while(_ --){
solve();
}
return 0;
}
描述
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。 输出最大价值。
输入格式 第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。
输出格式 输出一个整数,表示最大价值。
数据范围 0<N,V≤100 0<vi,wi,si≤100
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例:
输出样例:
10
思想
dp[i][j]
表示前i
个物品,总体积不超过j
的价值i
个 物品:dp[i][j] = dp[i - 1][j]
i
个物品k
个:dp[i][j] = dp[i - 1][j - k * v[i]] + k * w[i]
max()
j < k * v[i] || k > s[i]
时,不能选择物品,反之可选代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int dp[N][N];
int v[N], w[N], s[N];
void solve(){
int n, m;
cin >> n >>m;
for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i] >> s[i];
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
for(int k = 0; k * v[i] <= j && k <= s[i]; k ++){ //枚举选择物品的个数
dp[i][j] = max(dp[i][j],dp[i - 1][j - k * v[i]] + k * w[i]);
}
}
}
cout << dp[n][m] << endl;
}
int main(){
solve();
return 0;
}
描述
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。 输出最大价值。
输入格式 第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。
输出格式 输出一个整数,表示最大价值。
数据范围 0<N≤1000 0<V≤2000 0<vi,wi,si≤2000
输出样例:
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例:
10
思想
i
个物品,体积为v[i]
,价值为w[i]
,共有s[i]
件代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int dp[N];
int cnt; //用于记录新的捆绑物品的下标
int v[N], w[N];
void solve(){
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ++){
int a, b, s;
cin >> a >> b >> s;
int k = 1; //k从1开始捆绑
while(k < s){
cnt ++;
v[cnt] = k * a; //捆绑物品的体积
w[cnt] = k * b; //捆绑物品的价值
s -= k;
k <<= 1;
}
if(s){ //最后剩余的无法凑整的数
cnt ++;
v[cnt] = s * a;
w[cnt] = s * b;
}
}
for(int i = 1; i <= cnt; i ++){ //01背包一维优化求解
for(int j = m; j >= v[i]; j --){
dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
}
}
cout << dp[m] << endl;
}
int main(){
solve();
return 0;
}
描述
有 N 种物品和一个容量是 V 的背包。
物品一共有三类:
第一类物品只能用1次(01背包); 第二类物品可以用无限次(完全背包); 第三类物品最多只能用 si 次(多重背包); 每种体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。 输出最大价值。
输入格式 第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。
si=−1 表示第 i 种物品只能用1次; si=0 表示第 i 种物品可以用无限次; si>0 表示第 i 种物品可以使用 si 次; 输出格式 输出一个整数,表示最大价值。
数据范围 0<N,V≤1000 0<vi,wi≤1000 −1≤si≤1000
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
输出样例:
输出样例:
8
思想
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 3;
int dp[N];
int v[N], w[N];
void solve(){
int n, m;
cin >> n >> m;
int cnt = 0;
for(int i = 1; i <= n; i ++){
int a, b, s;
cin >> a >> b >> s;
if(s == -1) s = 1;
else if(s == 0) s = m / a;
int k = 1;
while(k < s){
cnt ++;
v[cnt] = k * a;
w[cnt] = k * b;
s -= k;
k <<= 1;
}
if(s){
cnt ++;
v[cnt] = s * a;
w[cnt] = s * b;
}
}
for(int i = 1; i <= cnt; i ++){
for(int j = m; j >= v[i]; j --){
dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
}
}
cout << dp[m] << endl;
}
int main(){
solve();
return 0;
}
描述
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个,同一组内的物品最多只能选一个。 每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。
求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式 第一行有两个整数 N,V,用空格隔开,分别表示物品组数和背包容量。
接下来有 N 组数据:
每组数据第一行有一个整数 Si,表示第 i 个物品组的物品数量; 每组数据接下来有 Si 行,每行有两个整数 vij,wij,用空格隔开,分别表示第 i 个物品组的第 j 个物品的体积和价值; 输出格式 输出一个整数,表示最大价值。
数据范围 0<N,V≤100 0<Si≤100 0<vij,wij≤100
输入样例:
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例:
8
思想
dp[j]
表示背包体积不超过j
时的价值v[i][k]
为i
组的第k
个物品的体积,w[i][k]
为i
组的第k
个物品的价值dp[j] = max(dp[j],dp[j - v[i][k]] + w[i][k])
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int dp[N];
int v[N][N], w[N][N];
void solve(){
int n, m;
cin >> n >>m;
for(int i = 1; i <= n; i ++){
int s[i];
cin >> s[i];
for(int j = 1; j <= s[i]; j ++){
cin >> v[i][j] >> w[i][j];
}
for(int j = m; j >= 0; j --){
for(int k = 1; k <= s[i]; k ++){
if(j >= v[i][k]) dp[j] = max(dp[j],dp[j - v[i][k]] + w[i][k]);
}
}
}
cout << dp[m] << endl;
}
int main(){
solve();
return 0;
}
描述
总公司拥有M台 相同 的高效设备,准备分给下属的N个分公司。
各分公司若获得这些设备,可以为国家提供一定的盈利。盈利与分配的设备数量有关。
问:如何分配这M台设备才能使国家得到的盈利最大?
求出最大盈利值。
分配原则:每个公司有权获得任意数目的设备,但总台数不超过设备数M。
输入格式 第一行有两个数,第一个数是分公司数N,第二个数是设备台数M;
接下来是一个N*M的矩阵,矩阵中的第 i 行第 j 列的整数表示第 i 个公司分配 j 台机器时的盈利。
输出格式 第一行输出最大盈利值;
接下N行,每行有2个数,即分公司编号和该分公司获得设备台数。
答案不唯一,输出任意合法方案即可。
数据范围 1≤N≤10, 1≤M≤15 输入样例:
3 3
30 40 50
20 30 50
20 25 30
输出样例:
70
1 1
2 1
3 1
思想
dp[i][j]
表示前i
个公司,使用服务器不超过j
获得的盈利的集合i
个公司的服务器:dp[i - 1][j]
i
个公司的k
个服务器:dp[i][j] = dp[i - 1][j - k] + w[i][k]
max()
:dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - k] + w[i][k])
num[i]
记录第i
个公司的服务器分配数量代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int dp[N][N];
int w[N][N];
int num[N];
void solve(){
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
cin >> w[i][j];
}
}
for(int i =1; i <= n; i ++){
for(int j = 0; j <= m; j ++){
for(int k = 0; k <= j; k ++){
dp[i][j] = max(dp[i][j],dp[i - 1][j - k] + w[i][k]);
}
}
}
int j = m;
for(int i = n; i ; i --){
for(int k = 1; k <= j; k ++){
if(dp[i][j] == dp[i - 1][j - k] + w[i][k]){
num[i] = k;
j -= k;
break;
}
}
}
cout << dp[n][m] << endl;
for(int i = 1; i <= n; i ++) cout << i << " " << num[i] << endl;
}
int main(){
solve();
return 0;
}
描述
有 N 件物品和一个容量是 V 的背包,背包能承受的最大重量是 M。
每件物品只能用一次。体积是 vi,重量是 mi,价值是 wi。
求解将哪些物品装入背包,可使物品总体积不超过背包容量,总重量不超过背包可承受的最大重量,且价值总和最大。 输出最大价值。
输入格式 第一行三个整数,N,V,M,用空格隔开,分别表示物品件数、背包容积和背包可承受的最大重量。
接下来有 N 行,每行三个整数 vi,mi,wi,用空格隔开,分别表示第 i 件物品的体积、重量和价值。
输出格式 输出一个整数,表示最大价值。
数据范围 0<N≤1000 0<V,M≤100 0<vi,mi≤100 0<wi≤1000
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6
输出样例:
输出样例:
8
思想
dp[i][j][k]
表示前i
个物品,体积不超过j
,且重量不超过k
的集合的价值i
个物品:dp[i][j][k] = dp[i - 1][j][k]
i
个物品:dp[i][j][k] = dp[i - 1][j - v[i]][k - m[i]] + w[i]
max()
:dp[i][j][k] = max(dp[i - 1][j][k],dp[i - 1][j - v[i]][k - m[i]] + w[i])
dp[j][k] = max(dp[j][k],dp[j - v[i]][k - m[i]] + w[i])
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int dp[N][N];
int v[N], m[N], w[N];
void solve(){
int n, V, M;
cin >> n >> V >> M;
for(int i = 1; i <= n; i ++) cin >> v[i] >> m[i] >> w[i];
for(int i = 1; i <= n; i ++){
for(int j = V; j >= v[i]; j --){
for(int k = M; k >= m[i]; k --){
dp[j][k] = max(dp[j][k],dp[j - v[i]][k - m[i]] + w[i]);
}
}
}
cout << dp[V][M] << endl;
}
int main(){
solve();
return 0;
}
描述
潜水员为了潜水要使用特殊的装备。
他有一个带2种气体的气缸:一个为氧气,一个为氮气。
让潜水员下潜的深度需要各种数量的氧和氮。
潜水员有一定数量的气缸。
每个气缸都有重量和气体容量。
潜水员为了完成他的工作需要特定数量的氧和氮。
他完成工作所需气缸的总重的最低限度的是多少?
例如:潜水员有5个气缸。每行三个数字为:氧,氮的(升)量和气缸的重量:
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119 如果潜水员需要5升的氧和60升的氮则总重最小为249(1,2或者4,5号气缸)。
你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。
输入格式 第一行有2个整数 m,n。它们表示氧,氮各自需要的量。
第二行为整数 k 表示气缸的个数。
此后的 k 行,每行包括ai,bi,ci,3个整数。这些各自是:第 i 个气缸里的氧和氮的容量及气缸重量。
输出格式 仅一行包含一个整数,为潜水员完成工作所需的气缸的重量总和的最低值。
数据范围 1≤m≤21, 1≤n≤79, 1≤k≤1000, 1≤ai≤21, 1≤bi≤79, 1≤ci≤800 输入样例:
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
输出样例:
249
思想
dp[i][j][k]
表示前i
个气瓶,氧气体积不少于j
,氮气体积不少于k
的重量i
个:dp[i][j][k] = dp[i - 1][j][k]
i
个:dp[i][j][k] = dp[i - 1][j - v[i]][k - w[i]] + m[i]
min()
:dp[i][j][k] = min(dp[i - 1][j][k],dp[i - 1][j - v[i]][k - w[i]] + m[i])
dp[0][0][0] = 0
,其余dp[i][j][k] = 0x3f3f3f3f
dp[j][k] = min(dp[j][k],dp[j - v[i]][k - w[i]] + m[i])
j - v[i] < 0
或者k - w[i] < 0
时也满足集合的定义,当j - v[i] < 0
或者k - w[i] < 0
时,视为j - v[i] = 0
或者k - w[i] = 0
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int dp[N][N];
int v[N], m[N], w[N];
void solve(){
int V, W, n;
cin >> V >> W >> n;
memset(dp, 0x3f, sizeof dp);
dp[0][0] = 0;
for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i] >> m[i];
for(int i = 1; i <= n; i ++){
for(int j = V; j >= 0; j --){
for(int k = W; k >= 0; k --){
dp[j][k] = min(dp[j][k],dp[max(0,j - v[i])][max(0,k - w[i])] + m[i]);
}
}
}
cout << dp[V][W] << endl;
}
int main(){
solve();
return 0;
}
描述
宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。
一天,小智和皮卡丘来到了小精灵狩猎场,里面有很多珍贵的野生宠物小精灵。
小智也想收服其中的一些小精灵。
然而,野生的小精灵并不那么容易被收服。
对于每一个野生小精灵而言,小智可能需要使用很多个精灵球才能收服它,而在收服过程中,野生小精灵也会对皮卡丘造成一定的伤害(从而减少皮卡丘的体力)。
当皮卡丘的体力小于等于0时,小智就必须结束狩猎(因为他需要给皮卡丘疗伤),而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。
当小智的精灵球用完时,狩猎也宣告结束。
我们假设小智遇到野生小精灵时有两个选择:收服它,或者离开它。
如果小智选择了收服,那么一定会扔出能够收服该小精灵的精灵球,而皮卡丘也一定会受到相应的伤害;如果选择离开它,那么小智不会损失精灵球,皮卡丘也不会损失体力。
小智的目标有两个:主要目标是收服尽可能多的野生小精灵;如果可以收服的小精灵数量一样,小智希望皮卡丘受到的伤害越小(剩余体力越大),因为他们还要继续冒险。
现在已知小智的精灵球数量和皮卡丘的初始体力,已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。
请问,小智该如何选择收服哪些小精灵以达到他的目标呢?
输入格式 输入数据的第一行包含三个整数:N,M,K,分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。
之后的K行,每一行代表一个野生小精灵,包括两个整数:收服该小精灵需要的精灵球的数量,以及收服过程中对皮卡丘造成的伤害。
输出格式 输出为一行,包含两个整数:C,R,分别表示最多收服C个小精灵,以及收服C个小精灵时皮卡丘的剩余体力值最多为R。
数据范围 0<N≤1000, 0<M≤500, 0<K≤100 输入样例1:
10 100 5
7 10
2 40
2 50
1 20
4 20
输出样例1:
3 30
思想
d[i][j][k]
表示前i
个小精灵,消耗精灵球不超过j
,且消耗皮卡丘体力不超过k
的收集到的精灵数量i
个小精灵:dp[i][j][k] = dp[i - 1][j][k]
i
个小精灵:dp[i][j][k] = dp[i - 1][j -v[i]][k - m[i]] + 1
max()
:dp[i][j][k] = max(dp[i - 1][j][k],dp[i - 1][j - v[i]][k - m[i]] + 1)
dp[j][k] = max(dp[j][k],dp[j - v[i]][k - m[i]] + 1)
dp[j][k]
,找到当dp[j][k] == dp[j][k - 1]
时,消耗最少的体力k
,用cnt
记录代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int dp[N][N];
int v[N], m[N];
void solve(){
int n, V, M;
cin >> V >> M >> n;
dp[0][0] = 0;
for(int i = 1; i <= n; i ++) cin >> v[i] >> m[i];
for(int i = 1; i <= n; i ++){
for(int j = V; j >= v[i]; j --){
for(int k = M - 1; k >= m[i]; k --){
dp[j][k] = max(dp[j][k],dp[j - v[i]][k - m[i]] + 1);
}
}
}
int cnt = 0x3f3f3f3f;
for(int i = 0; i <= V; i ++){
for(int j = 0; j <= M - 1; j ++){
if(dp[i][j] == dp[V][M - 1]) cnt = min(cnt,j);
}
}
cout << dp[V][M - 1] << " " << M - cnt << endl;
}
int main(){
solve();
return 0;
}
描述
有 N 个物品和一个容量是 V 的背包。
物品之间具有依赖关系,且依赖关系组成一棵树的形状。如果选择一个物品,则必须选择它的父节点。
如果选择物品5,则必须选择物品1和2。这是因为2是5的父节点,1是2的父节点。
每件物品的编号是 i,体积是 vi,价值是 wi,依赖的父节点编号是 pi。物品的下标范围是 1…N。
求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式 第一行有两个整数 N,V,用空格隔开,分别表示物品个数和背包容量。
接下来有 N 行数据,每行数据表示一个物品。 第 i 行有三个整数 vi,wi,pi,用空格隔开,分别表示物品的体积、价值和依赖的物品编号。 如果 pi=−1,表示根节点。 数据保证所有物品构成一棵树。
输出格式 输出一个整数,表示最大价值。
数据范围 1≤N,V≤100 1≤vi,wi≤100 父节点编号范围:
内部结点:1≤pi≤N; 根节点 pi=−1;
输出样例:
5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2
输出样例:
11
思想
dp[i][j]
表示第i
个物品为根节点的字数,且选上i
选法的体积不超过j
的价值i
:则其子节点的价值之和为0;i
:递归处理所有子节点,选择最大的字节点的最大价值的子树代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int dp[N][N];
int e[N], ne[N], h[N], idx;
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int n, m;
int v[N], w[N];
void dfs(int u){
for(int i = h[u]; i != -1; i = ne[i]){
int son = e[i];
dfs(son);
for(int j = m - v[u]; j >= 0; j --){
for(int k = 0; k <= j; k ++){
dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[son][k]);
}
}
}
for(int i = m; i >= v[u]; i --) dp[u][i] = dp[u][i - v[u]] + w[u];
for(int i = 0; i < v[u]; i ++) dp[u][i] =0;
}
void solve(){
memset(h, -1, sizeof h);
cin >> n >> m;
int root;
for(int i = 1; i <= n; i ++){
int p;
cin >> v[i] >> w[i] >> p;
if(p == -1) root = i;
if(p){
add(p, i);
}
}
dfs(root);
cout << dp[root][m] << endl;
}
int main(){
solve();
return 0;
}
描述
金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。
更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。
今天一早,金明就开始做预算了,他把想买的物品分为两类:主件与附件,附件是从属于某个主件的
如果要买归类为附件的物品,必须先买该附件所属的主件。
每个主件可以有0个、1个或2个附件。
附件不再有从属于自己的附件。
金明想买的东西很多,肯定会超过妈妈限定的N元。
于是,他把每件物品规定了一个重要度,分为5等:用整数1~5表示,第5等最重要。
他还从因特网上查到了每件物品的价格(都是10元的整数倍)。
他希望在不超过N元(可以等于N元)的前提下,使每件物品的价格与重要度的乘积的总和最大。
设第j件物品的价格为v[j],重要度为w[j],共选中了k件物品,编号依次为j1,j2,…,jk,则所求的总和为:
v[j1]∗w[j1]+v[j2]∗w[j2]+…+v[jk]∗w[jk](其中*为乘号)
请你帮助金明设计一个满足要求的购物单。
输入格式 输入文件的第1行,为两个正整数,用一个空格隔开:N m,其中N表示总钱数,m为希望购买物品的个数。
从第2行到第m+1行,第j行给出了编号为j-1的物品的基本数据,每行有3个非负整数v p q,其中v表示该物品的价格,p表示该物品的重要度(1~5),q表示该物品是主件还是附件。
如果q=0,表示该物品为主件,如果q>0,表示该物品为附件,q是所属主件的编号。
输出格式 输出文件只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<200000)。
数据范围 N<32000,m<60,v<10000
输出样例:
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
输出样例:
2200
思想
dp[i][j]
表示前i
个物品,总体积不超过j
的价值i
个物品:dp[i][j] = dp[i - 1][j]
i
个物品:dp[i][j] = dp[i - 1][j - v[i]] + w[i]
代码
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int, int> PII;
const int N = 70, M = 32010;
int n, m;
PII ma[N];
vector<PII> sv[N];
int dp[M];
void solve(){
cin >> m >> n;
for (int i = 1; i <= n; i ++ ) {
int v, w, q;
cin >> v >> w >> q;
if (!q) ma[i] = {v, v * w};
else sv[q].push_back({v, v * w});
}
for (int i = 1; i <= n; i ++ )
if (ma[i].fi) {
for (int j = m; j >= 0; j -- ) {
for (int k = 0; k < 1 << sv[i].size(); k ++ ) {
int v = ma[i].fi, w = ma[i].se;
for (int u = 0; u < sv[i].size(); u ++ )
if (k >> u & 1) {
v += sv[i][u].fi;
w += sv[i][u].se;
}
if (j >= v) dp[j] = max(dp[j], dp[j - v] + w);
}
}
}
cout << dp[m] << endl;
}
int main(){
solve();
return 0;
}
描述
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出 最优选法的方案数。注意答案可能很大,请输出答案模 109+7 的结果。
输入格式 第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。
输出格式 输出一个整数,表示 方案数 模 109+7 的结果。
数据范围 0<N,V≤1000 0<vi,wi≤1000
输出样例:
4 5
1 2
2 4
3 4
4 6
输出样例:
2
思想
cnt[j]
表示背包容积为j
时最佳的方案cnt[j] = cnt[j - v[i]]
cnt[j] = cnt[j] + cnt[j - v[i]]
cnt[j] = 1
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int mod = 1e9 + 7;
int dp[N];
int cnt[N];
int v[N], w[N];
void solve(){
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
for(int i = 0; i <= m; i ++) cnt[i] = 1;
for(int i = 1; i <= n; i ++){
for(int j = m; j >= v[i]; j --){
int t = dp[j - v[i]] + w[i];
if(t > dp[j]){
dp[j] = t;
cnt[j] = cnt[j - v[i]];
}
else if(t == dp[j]){
cnt [j] = (cnt[j] + cnt[j - v[i]]) % mod;
}
}
}
cout << cnt[m] << endl;
}
int main(){
solve();
return 0;
}
描述
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出 字典序最小的方案。这里的字典序是指:所选物品的编号所构成的序列。物品的编号范围是 1…N。
输入格式 第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。
输出格式 输出一行,包含若干个用空格隔开的整数,表示最优解中所选物品的编号序列,且该编号序列的字典序最小。
物品编号范围是 1…N。
数据范围 0<N,V≤1000 0<vi,wi≤1000
输出样例:
4 5
1 2
2 4
3 4
4 6
输出样例:
1 4
思想
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int dp[N][N];
int v[N], w[N];
void solve(){
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
for(int i = n; i >= 1; i --){
for(int j = 0; j <= m; j ++){
dp[i][j] = dp[i + 1][j];
if(j >= v[i]) dp[i][j] = max(dp[i][j],dp[i + 1][j - v[i]] + w[i]);
}
}
int j = m;
for(int i = 1; i <= n; i ++){
if(j >= v[i] && dp[i][j] == dp[i + 1][j - v[i]] + w[i]){
cout << i << ' ';
j -= v[i];
}
}
}
int main(){
solve();
return 0;
}