很經(jīng)典的分組背包題目了，每一項課程學習不同的天數(shù)會有不同的收益，所以每一門課程的不同學習天數(shù)就是一個組別，最多只能選擇其中的一個。 可以用滾動數(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]表示使用金錢為y時前x組物品中能獲得的最大值，所以只要初始化dp數(shù)組為負無窮大，當有一組一雙都買不了時，接下來的遞推結果就都是負數(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)買過鞋了再買這雙鞋選擇最優(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]使用金錢為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;}給出你有的硬幣種類及對應的數(shù)量，讓你求出能組成多少種小于等于n的價值。應該可以用多重背包解，這里用的記憶化的方法，dp為bool型，1表示這種狀態(tài)可以達到。 used數(shù)組記錄當前價值用了幾個當前硬幣，這種方法只適用于此類題。
#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;}有總數(shù)限制的背包，通常做法就是給dp數(shù)組加維度，dp[a][b]忍耐度使用a,總數(shù)量為b時獲得的最大經(jīng)驗值。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,總數(shù)量為b時獲得的最大經(jīng)驗值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循環(huán)遞推時，只要滿足狀態(tài)轉(zhuǎn)移方程中的東西在這之前已經(jīng)計算過就行，循環(huán)的嵌套內(nèi)外層交換不一定會影響結果。
新聞熱點
疑難解答
