杭州建设网站公司哪家好,做教育类的网站名,重庆网站建设 优化,想学服装设计一、装箱问题 (裸题)
有一个箱子容量为 V#xff0c;同时有 n 个物品#xff0c;每个物品有一个体积#xff08;正整数#xff09;。 要求 n 个物品中#xff0c;任取若干个装入箱内#xff0c;使箱子的剩余空间为最小。
输入 第一行是一个整数 V (0 V ≤ 20000)同时有 n 个物品每个物品有一个体积正整数。 要求 n 个物品中任取若干个装入箱内使箱子的剩余空间为最小。
输入 第一行是一个整数 V (0 V ≤ 20000)表示箱子容量。 第二行是一个整数 n (0 n ≤ 30)表示物品数。 接下来 n 行每行一个正整数不超过10000分别表示这 n 个物品的各自体积。 输出 一个整数表示箱子剩余空间。
Input 24 6 8 3 12 7 9 7 Output 0
解析 求所剩空间最小可转化成所用空间最大。 每个物品的价值就是体积。 就可转化成 从前 n 个物品中不超过总体积最大价值是多少。
#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pairint,int PII;
const double PIacos(-1.0);
const int N2e610;
int n,u;
int v[N];
int f[N];
void solve()
{cinun;for (int i1;in;i) cinv[i];for (int i1;in;i)for (int ju;jv[i];j--)f[j]max(f[j],f[j-v[i]]v[i]);coutu-f[u];
}
signed main()
{ios;int T1;//cinT;while (T--) solve();return 0;
} 二、 宠物小精灵之收服 (二维费用)
宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。 一天小智和皮卡丘来到了小精灵狩猎场里面有很多珍贵的野生宠物小精灵。 小智也想收服其中的一些小精灵。 然而野生的小精灵并不那么容易被收服。 对于每一个野生小精灵而言小智可能需要使用很多个精灵球才能收服它而在收服过程中野生小精灵也会对皮卡丘造成一定的伤害从而减少皮卡丘的体力。 当皮卡丘的体力小于等于0时小智就必须结束狩猎因为他需要给皮卡丘疗伤而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。 当小智的精灵球用完时狩猎也宣告结束。 我们假设小智遇到野生小精灵时有两个选择收服它或者离开它。 如果小智选择了收服那么一定会扔出能够收服该小精灵的精灵球而皮卡丘也一定会受到相应的伤害如果选择离开它那么小智不会损失精灵球皮卡丘也不会损失体力。 小智的目标有两个主要目标是收服尽可能多的野生小精灵如果可以收服的小精灵数量一样小智希望皮卡丘受到的伤害越小剩余体力越大因为他们还要继续冒险。 现在已知小智的精灵球数量和皮卡丘的初始体力已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。 请问小智该如何选择收服哪些小精灵以达到他的目标呢
输入 输入数据的第一行包含三个整数N (0 N ≤ 1000)M (0 M ≤ 500)K (0 K ≤ 100)分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。 之后的K行每一行代表一个野生小精灵包括两个整数收服该小精灵需要的精灵球的数量以及收服过程中对皮卡丘造成的伤害。
输出 输出为一行包含两个整数CR分别表示最多收服C个小精灵以及收服C个小精灵时皮卡丘的剩余体力值最多为R。
Input 10 100 5 7 10 2 40 2 50 1 20 4 20 Output 3 30 int n,u,k; int v1[N],v2[N],f[N][N][N],s[N][N][N]; void solve() { cinukn; for (int i1;in;i) cinv1[i]v2[i]; for (int i1;in;i) for (int j1;ju;j) for (int l1;lk;l) { f[i][j][l]f[i-1][j][l]; s[i][j][l]s[i-1][j][l]; if (j-v1[i]0l-v2[i]0) { if (f[i][j][l]f[i-1][j-v1[i]][l-v2[i]]1) f[i][j][l]f[i-1][j-v1[i]][l-v2[i]]1,s[i][j][l]s[i-1][j-v1[i]][l-v2[i]]v2[i]; else if (f[i][j][l]f[i-1][j-v1[i]][l-v2[i]]1s[i][j][l]s[i-1][j-v1[i]][l-v2[i]]v2[i]) s[i][j][l]s[i-1][j-v1[i]][l-v2[i]]v2[i]; } } coutf[n][u][k-1] k-s[n][u][k-1]; } 解析 题目很长但是能看出来是01背包问题不过是多加了一维。 所求 从前n个小精灵中选 在不超过小智精灵球的数量对皮卡丘的伤害值小于体力值的情况下尽可能地多收服小精灵最多能收服多少小精灵和皮卡丘体力剩余最大。 正常是三维 f[i][j][k], 不过空间肯定不够所以得优化代码降一维就可以了。
//代码一:
#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pairint,int PII;
const double PIacos(-1.0);
const int N1010;
int n,u,k;
int v1[N],v2[N],f[N][N],s[N][N];
void solve()
{cinukn;for (int i1;in;i) cinv1[i]v2[i];for (int i1;in;i)for (int ju;jv1[i];j--)for (int lk-1;lv2[i];l--){if (f[j][l]f[j-v1[i]][l-v2[i]]1) f[j][l]f[j-v1[i]][l-v2[i]]1,s[j][l]s[j-v1[i]][l-v2[i]]v2[i];else if (f[j][l]f[j-v1[i]][l-v2[i]]1s[j][l]s[j-v1[i]][l-v2[i]]v2[i]) s[j][l]s[j-v1[i]][l-v2[i]]v2[i];}coutf[u][k-1] k-s[u][k-1];
}
signed main()
{ios;int T1;//cinT;while (T--) solve();return 0;
}//代码二 (更简便)
#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pairint,int PII;
const double PIacos(-1.0);
const int N1010;
int n,u,k;
int v1[N],v2[N],f[N][N];
void solve()
{cinukn;for (int i1;in;i) cinv1[i]v2[i];for (int i1;in;i)for (int ju;jv1[i];j--)for (int lk-1;lv2[i];l--){f[j][l]max(f[j][l],f[j-v1[i]][l-v2[i]]1);}coutf[u][k-1] ;int cntk-1;for (int ik-1;i0;i--){if (f[u][i]f[u][k-1]) cnti;}coutk-cnt;
}
signed main()
{ios;int T1;//cinT;while (T--) solve();return 0;
} 三、数字组合 (方案数)
给定 N 个正整数 A1,A2,…,AN从中选出若干个数使它们的和为 M求有多少种选择方案。
输入 第一行包含两个整数 N 和 M (1 ≤ N ≤ 100,1 ≤ M ≤ 10000)。 第二行包含 N 个整数表示 A1,A2,…,AN(1 ≤ Ai ≤ 1000)。 输出 包含一个整数表示可选方案数。
Input 4 4 1 1 2 2 Output 3 解析 将 M 看成背包总体积 将每个数看成每个物品 所求 从前 n 个物品中选恰好总体积是 M 的集合 的方案数。 状态转移f[i][j]f[i-1][j]f[i-1][j-v[i]];不过要记住要初始化哦
//代码一
#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pairint,int PII;
const double PIacos(-1.0);
const int N110,M1e410;
int n,m;
int v[N],f[N][M];
void solve()
{cinnm;for (int i1;in;i) cinv[i];for (int i0;in;i) f[i][0]1; //初始化for (int i1;in;i)for (int j1;jm;j){f[i][j]f[i-1][j];if (j-v[i]0) f[i][j] f[i-1][j-v[i]];}coutf[n][m];
}
signed main()
{ios;int T1;//cinT;while (T--) solve();return 0;
}//代码二 (降一维)
#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pairint,int PII;
const double PIacos(-1.0);
const int N1e410;
int n,m;
int f[N],v[N];
void solve()
{cinnm;for (int i1;in;i) cinv[i];f[0]1;for (int i1;in;i)for (int jm;jv[i];j--)f[j] f[j-v[i]];coutf[m];
}
signed main()
{ios;int T1;//cinT;while (T--) solve();return 0;
}
