几道与背包九讲相关的题目（HDU - 1712，3033，2844，2159）

2019-11-10 17:25:15

字体：大中小

来源：转载

供稿：网友

ACboy needs your help HDU - 1712

很经典的分组背包题目了，每一项课程学习不同的天数会有不同的收益，所以每一门课程的不同学习天数就是一个组别，最多只能选择其中的一个。可以用滚动数组优化空间。

#include<iostream>#include<string.h>#include<algorithm>#include<stdio.h>using namespace std;int n,m;int pp[105][105];//pp[n][x]是第n组int dp[105];int main(){ while (scanf("%d%d",&n,&m),n+m){ for (int i = 1; i <= n; i++){ for (int j = 1; j <= m; j++){ scanf("%d", &pp[i][j]); } } memset(dp, 0, sizeof(dp)); for (int i = 1; i <= n; i++){//zu for (int j = m; j >= 0; j--){ for (int k = 1; k <= m; k++){//ge if (j >= k)dp[j] = max(dp[j], dp[j - k] + pp[i][k]); } } } PRintf("%d/n", dp[m]); } return 0;}

I love sneakers! HDU - 3033

也是分组背包，但是要求的是每组至少每一双，dp[x][y]表示使用金钱为y时前x组物品中能获得的最大值，所以只要初始化dp数组为负无穷大，当有一组一双都买不了时，接下来的递推结果就都是负数。 dp[i][k] = max(dp[i][k], max(dp[i - 1][k - vec[i][j].need] + vec[i][j].val, dp[i][k - vec[i][j].need] + vec[i][j].val))状态转移是比较不买这双鞋，这组第一次买这双鞋，这组已经买过鞋了再买这双鞋选择最优的状态。

#include<iostream>#include<string.h>#include<algorithm>#include<stdio.h>#include<vector>using namespace std;int n, m, k;struct p{ int need; int val;};vector<p> vec[12];int dp[12][10005];//dp[x][y]使用金钱为y时前x组物品中能获得的最大值int main(){ int x, y, z; while (~scanf("%d%d%d", &n, &m, &k)){ for (int i = 1; i <= k; i++)vec[i].clear(); for (int i = 0; i < n; i++){ scanf("%d%d%d", &x, &y, &z); vec[x].push_back({ y, z }); } memset(dp, -0x3f, sizeof(dp)); for (int i = 0; i <= m; i++)dp[0][i] = 0; for (int i = 1; i <= k; i++){ int size = vec[i].size(); for (int j = 0; j < size; j++){ for (int k = m; k >= vec[i][j].need; k--){ dp[i][k] = max(dp[i][k], max(dp[i - 1][k - vec[i][j].need] + vec[i][j].val, dp[i][k - vec[i][j].need] + vec[i][j].val)); } } } if (dp[k][m] >= 0){ printf("%d/n", dp[k][m]); } else{ printf("Impossible/n"); } } return 0;}

Coins HDU - 2844

给出你有的硬币种类及对应的数量，让你求出能组成多少种小于等于n的价值。应该可以用多重背包解，这里用的记忆化的方法，dp为bool型，1表示这种状态可以达到。 used数组记录当前价值用了几个当前硬币，这种方法只适用于此类题。

#include<iostream>#include<string.h>#include<algorithm>#include<stdio.h>using namespace std;int n,m;int a[105];int c[105];int used[100005];bool dp[100005];//前n个物品int main(){ while (scanf("%d%d", &n, &m), m + n){ for (int i = 1; i <= n; i++){ scanf("%d", &a[i]); } for (int i = 1; i <= n; i++){ scanf("%d", &c[i]); } memset(dp, 0, sizeof(dp)); dp[0] = 1; int ans = 0; for (int i = 1; i <= n; i++){ memset(used, 0, sizeof(used)); for (int j = a[i]; j <= m; j++){ if (dp[j - a[i]] && !dp[j] && used[j - a[i]] < c[i]){ dp[j] = 1; used[j] = used[j - a[i]] + 1; ans++; } } } printf("%d/n", ans); } return 0;}

FATE HDU - 2159

有总数限制的背包，通常做法就是给dp数组加维度，dp[a][b]忍耐度使用a,总数量为b时获得的最大经验值。dp[j][k] = max(dp[j][k], dp[j - edu[i]][k - 1] + eexp[i])

#include<iostream>#include<string.h>#include<algorithm>#include<stdio.h>using namespace std;int n,m,k,s;int eexp[105];int edu[105];int dp[105][105];//dp[a][b]忍耐度使用a,总数量为b时获得的最大经验值int main(){ while (~scanf("%d%d%d%d",&n,&m,&k,&s)){ for (int i = 1; i <= k; i++){ scanf("%d%d", &eexp[i], &edu[i]); } memset(dp, 0, sizeof(dp)); for (int i = 1; i <= k; i++){ for (int k = 1; k <= s; k++){ for (int j = edu[i]; j <= m; j++){ dp[j][k] = max(dp[j][k], dp[j - edu[i]][k - 1] + eexp[i]); } } } int ans = 0x3f3f3f; for (int i = 0; i <= m; i++){ for (int j = 0; j <= s; j++){ if (dp[i][j] >= n){ ans = min(ans, i); } } } if (ans == 0 || ans > m){ printf("%d/n", -1); } if (ans <= m){ printf("%d/n",m-ans); } } return 0;}

关于dp循环递推时，只要满足状态转移方程中的东西在这之前已经计算过就行，循环的嵌套内外层交换不一定会影响结果。

上一篇：SQL SERVER数据库修改是否区分大小写

下一篇：每日一练之自适应中值滤波器(基于OpenCV实现)