幾道與背包九講相關(guān)的題目（HDU - 1712，3033，2844，2159）

2019-11-09 19:14:48

字體：大中小

供稿：網(wǎng)友

ACboy needs your help HDU - 1712

很經(jīng)典的分組背包題目了，每一項(xiàng)課程學(xué)習(xí)不同的天數(shù)會(huì)有不同的收益，所以每一門(mén)課程的不同學(xué)習(xí)天數(shù)就是一個(gè)組別，最多只能選擇其中的一個(gè)。可以用滾動(dòng)數(shù)組優(yōu)化空間。

#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]); } } } I love sneakers! HDU - 3033

也是分組背包，但是要求的是每組至少每一雙，dp[x][y]表示使用金錢(qián)為y時(shí)前x組物品中能獲得的最大值，所以只要初始化dp數(shù)組為負(fù)無(wú)窮大，當(dāng)有一組一雙都買不了時(shí)，接下來(lái)的遞推結(jié)果就都是負(fù)數(shù)。 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))狀態(tài)轉(zhuǎn)移是比較不買這雙鞋，這組第一次買這雙鞋，這組已經(jīng)買過(guò)鞋了再買這雙鞋選擇最優(yōu)的狀態(tài)。

#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]使用金錢(qián)為y時(shí)前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

給出你有的硬幣種類及對(duì)應(yīng)的數(shù)量，讓你求出能組成多少種小于等于n的價(jià)值。應(yīng)該可以用多重背包解，這里用的記憶化的方法，dp為bool型，1表示這種狀態(tài)可以達(dá)到。 used數(shù)組記錄當(dāng)前價(jià)值用了幾個(gè)當(dāng)前硬幣，這種方法只適用于此類題。

#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個(gè)物品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;}