題干：

問(wèn)題描述

　　給n個(gè)有序整數(shù)對(duì)ai bi，你需要選擇一些整數(shù)對(duì) 使得所有你選定的數(shù)的ai+bi的和最大。并且要求你選定的數(shù)對(duì)的ai之和非負(fù)，bi之和非負(fù)。

輸入格式

　　輸入的第一行為n，數(shù)對(duì)的個(gè)數(shù)
　　以下n行每行兩個(gè)整數(shù) ai bi

輸出格式

　　輸出你選定的數(shù)對(duì)的ai+bi之和

樣例輸入

5
-403 -625
-847 901
-624 -708
-293 413
886 709

樣例輸出

1715

數(shù)據(jù)規(guī)模和約定

　　1<=n<=100
　　-1000<=ai,bi<=1000

時(shí)間限制：1.0s ? 內(nèi)存限制：256.0MB

解題報(bào)告：

不直接計(jì)算選定的數(shù)的ai+bi的和，而是轉(zhuǎn)化為計(jì)算在ai的和一定的情況下盡量使選定的bi的和最大。于是變成為一個(gè)01背包問(wèn)題，ai的值作為物體的重量，bi的值作為該物體的價(jià)值。首先過(guò)濾掉所有ai和bi均小于0的數(shù)對(duì)，令dp[i][j]表示前i個(gè)數(shù)對(duì)，選定的ai的和為j的情況下bi的和的最大值，將dp[i][j]初始化為-INF，再將所有已知合法情況初始化：dp[i][a[i]] = b[i]，之后dp[i][j] = max(dp[i - 1][j], dp[i][j])，若j - a[i]存在，dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i]] + b[i])。最后再統(tǒng)一加偏移量ZERO。值得注意的是，這個(gè)背包問(wèn)題雖然也可以?xún)?yōu)化成一維，但是沒(méi)必要，如果優(yōu)化成一維，對(duì)于這題代碼不會(huì)更簡(jiǎn)練反而會(huì)復(fù)雜不少，因?yàn)檫@題初始化的時(shí)候不能只對(duì)二維數(shù)組的第一行進(jìn)行初始化，需要每一行都有一個(gè)值進(jìn)行初始化，所以最好的辦法就是直接開(kāi)二維數(shù)組做最樸素的01背包，而且這題空間給的足夠大，所以不需要擔(dān)心MLE的問(wèn)題。

AC代碼：（空間大概78MB）

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; int tot; int a[101],b[101]; int dp[101][200000 + 5];//截止到第i個(gè)，a[i]和為j的情況下，b[i] 的最大值 int zero = 100000; const int INF = 0x3f3f3f3f; int main() {int n;cin>>n;for(int x,y,i = 1; i<=n; i++) {scanf("%d%d",&x,&y);if(x < 0 && y < 0) continue;a[++tot] = x, b[tot] = y;} for(int i = 0; i<=tot; i++) {for(int j = -100000; j<=100000; j++) {dp[i][j+ zero] = -INF;}}for(int i = 1; i<=tot; i++) {dp[i][a[i]+ zero] = b[i];}for(int i = 2; i<=tot; i++) {for(int j = -100000; j<=100000; j++) {if(dp[i-1][j+ zero] != -INF) dp[i][j+ zero] = max(dp[i][j+zero],dp[i-1][j+ zero]);if(j - a[i] + zero >= 0 && j - a[i] + zero <= 200000) //這句必須加。 dp[i][j+ zero] = max(dp[i][j+ zero] , dp[i-1][j-a[i]+ zero] + b[i]);}}int ans = 0;for(int j = 100000; j>=0; j--) {if(dp[tot][j+ zero] >= 0) ans = max(ans, dp[tot][j+ zero] + j);}printf("%d\n",ans);return 0 ;}

或者這樣也可以過(guò)：（空間162.9MB）

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; int tot; int a[MAX],b[MAX]; int dp[105][400000 + 5];//截止到第i個(gè)，a[i]和為j的情況下，b[i] 的最大值 int zero = 100000; const int INF = 0x3f3f3f3f; int main() {int n;cin>>n;for(int x,y,i = 1; i<=n; i++) {scanf("%d%d",&x,&y);if(x < 0 && y < 0) continue;a[++tot] = x, b[tot] = y;} for(int i = 0; i<=tot; i++) {for(int j = -100000; j<=300000; j++) {//這里變了dp[i][j+ zero] = -INF;}}for(int i = 1; i<=tot; i++) {dp[i][a[i]+ zero] = b[i];}for(int i = 2; i<=tot; i++) {for(int j = -100000; j<=100000; j++) {if(dp[i-1][j+ zero] != -INF) dp[i][j+ zero] = max(dp[i][j+zero],dp[i-1][j+ zero]);if(j - a[i] + zero >= 0 )//這里變了dp[i][j+ zero] = max(dp[i][j+ zero] , dp[i-1][j-a[i]+ zero] + b[i]);}}int ans = 0;for(int j = 100000; j>=0; j--) {if(dp[tot][j+ zero] >= 0) ans = max(ans, dp[tot][j+ zero] + j);}printf("%d\n",ans);return 0 ;}

或者這樣：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; int tot; int a[MAX],b[MAX]; int dp[105][400000 + 5];//截止到第i個(gè)，a[i]和為j的情況下，b[i] 的最大值 int zero = 100000; const int INF = 0x3f3f3f3f; int main() {int n;cin>>n;for(int x,y,i = 1; i<=n; i++) {scanf("%d%d",&x,&y);if(x < 0 && y < 0) continue;a[++tot] = x, b[tot] = y;} for(int i = 0; i<=tot; i++) {for(int j = -100000; j<=300000; j++) {dp[i][j+ zero] = -INF;}}dp[0][zero] = 0; // for(int i = 1; i<=tot; i++) { // dp[i][a[i]+ zero] = b[i]; // }for(int i = 1; i<=tot; i++) {for(int j = -100000; j<=100000; j++) {if(dp[i-1][j+ zero] != -INF) dp[i][j+ zero] = max(dp[i][j+zero],dp[i-1][j+ zero]);if(j - a[i] + zero >= 0 )dp[i][j+ zero] = max(dp[i][j+ zero] , dp[i-1][j-a[i]+ zero] + b[i]);}}int ans = 0;for(int j = 100000; j>=0; j--) {if(dp[tot][j+ zero] >= 0) ans = max(ans, dp[tot][j+ zero] + j);}printf("%d\n",ans);return 0 ;}

當(dāng)然，如果你連if(j - a[i] + zero >= 0 )也不想寫(xiě)，那就可以直接ZERO設(shè)為200000就行了。

總結(jié)：

? 首先需要知道他和0-1背包還是有區(qū)別的，因?yàn)?-1背包是可以不初始化成-INF的，但是那樣表示的是可以表示的最大價(jià)值（因?yàn)閮r(jià)值都是正數(shù)），所以0可以當(dāng)成是非法狀態(tài)。而這個(gè)題，必須初始化成-INF，因?yàn)檫@題所謂的“價(jià)值”可以是負(fù)數(shù)，我們需要新設(shè)置一個(gè)非法狀態(tài)，并且把唯一一個(gè)合法狀態(tài)設(shè)置好dp[0][zero]=0;來(lái)方便后面的轉(zhuǎn)移。其實(shí)這樣說(shuō)來(lái)，就可以改成一維的0-1背包了。

錯(cuò)誤代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; int tot; int a[MAX],b[MAX]; int dp[400000 + 5];//截止到第i個(gè)，a[i]和為j的情況下，b[i] 的最大值 int zero = 100000; const int INF = 0x3f3f3f3f; int main() {int n;cin>>n;for(int x,y,i = 1; i<=n; i++) {scanf("%d%d",&x,&y);if(x < 0 && y < 0) continue;a[++tot] = x, b[tot] = y;} for(int j = -100000; j<=300000; j++) {dp[j+ zero] = -INF;}dp[zero] = 0;for(int i = 1; i<=tot; i++) {for(int j = 100000; j>=-100000; j--) {if(j - a[i] + zero >= 0) dp[j+ zero] = max(dp[j+ zero] , dp[j-a[i]+ zero] + b[i]);}}int ans = 0;for(int j = 100000; j>=0; j--) {if(dp[j+ zero] >= 0) ans = max(ans, dp[j+ zero] + j);}printf("%d\n",ans);return 0 ;}

但是仔細(xì)一想，這樣是錯(cuò)誤的，因?yàn)榫偷貪L動(dòng)的前提是，后面的數(shù)只能用到前面的數(shù)，而你這個(gè)題，a[i]有正有負(fù)，所以可能用到前面的狀態(tài)也可能用到后面的狀態(tài)，所以不能優(yōu)化成一維。

總結(jié)

以上是生活随笔為你收集整理的【蓝桥杯官网试题 - 算法提高 】求最大值 （dp，0-1背包）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。