01 背包

題意：

　　在N件物品取出若干件放在容量為W的背包里，每件物品的體積為W1，W2……Wn（Wi為整數），與之相對應的價值為P1,P2……Pn（Pi為整數）。求背包能夠容納的最大價值。

f[i][v] = max{ f[i-1][v] , f[i-1][ v-c[i] ] + w[i] }

?

#include <iostream> #include <cstdio> #include <cmath> using namespace std; const int maxn = 100 + 5;int n ,w; int v[maxn],s[maxn]; int dp[2][10010];int main() {cin>> n >> w;for(int i=1;i <= n;i++){cin >> v[i] >> s[i];}int now = 1,pre = 0;for(int i=1;i <= n;i++){for(int j=0;j<=w;j++){if(j < v[i])dp[now][j] = dp[pre][j];elsedp[now][j] = max(dp[pre][j] , dp[pre][j-v[i]]+s[i]); // 不選 就是dp[i-1][j]//選就是dp[i-1][j-v[i]]+s[i] }swap (now,pre);}cout<< dp[pre][w]<<endl;return 0; } 01 背包

?下面是優化過內存的

#include <iostream> #include <cstdio> #include <cmath> #include <string.h> using namespace std; const int maxn = 100 + 5;int n ,w; int v[maxn],s[maxn]; int dp[10010];int main() {cin>> n >> w;for(int i=1;i <= n;i++){cin >> v[i] >> s[i];}memset(dp,0,sizeof(dp));for(int i=1;i <= n;i++){for(int j=w;j >= v[i];j--)//從上面一個狀態轉移 但是倒著寫 上面一個狀態就不會轉移了dp[j] = max(dp[j] , dp[j-v[i]]+s[i]);}cout<< dp[w]<<endl;return 0; } 01 背包優化

?

完全背包

題意：

　　在N種 物品取出若干件放在容量為W的背包里，每件物品的體積為W1，W2……Wn（Wi為整數），與之相對應的價值為P1,P2……Pn（Pi為整數）。求背包能夠容納的最大價值。

思路：

　　完全背包和01 背包的區別就是 能夠存儲的物品可以挑選多次

所以 轉移方程也就變成了?dp[i][j] = max(dp[i-1][j] , dp[i][j-v[i]]+s[i]); // 不選 就是dp[i-1][j] ?選就用dp[i][j-v[i]]+s[i]

//而01背包 就是dp[i][j] = max(dp[i-1][j] , dp[i-1][j-v[i]]+s[i])

?

f[i][v] = max{ f[i-1][v-k*c[i]] + k*w[i] | 0 <= k*c[i] <= v}

#include <iostream> #include <cstdio> #include <cmath> using namespace std; const int maxn = 100 + 5;int n ,w; int v[maxn],s[maxn]; int dp[2][10010];int main() {cin>> n >> w;for(int i=1;i <= n;i++){cin >> v[i] >> s[i];}int now = 1,pre = 0;for(int i=1;i <= n;i++){for(int j=0;j<=w;j++){if(j < v[i])dp[now][j] = dp[pre][j];elsedp[now][j] = max(dp[pre][j] , dp[now][j-v[i]]+s[i]); // 不選 就是dp[i-1][j]//選就是dp[i][j-v[i]]+s[i] }swap (now,pre);}cout<< dp[pre][w]<<endl;return 0; } 完全背包

下面也是優化過的

#include <iostream> #include <cstdio> #include <cmath> #include <string.h> using namespace std; const int maxn = 100 + 5;int n ,w; int v[maxn],s[maxn]; int dp[10010];int main() {cin>> n >> w;for(int i=1;i <= n;i++){cin >> v[i] >> s[i];}memset(dp,0,sizeof(dp));for(int i=1;i <= n;i++){for(int j=v[i];j <= w;j++)//可以從上面一個狀態轉移 正著寫 就能覆蓋上次的計算了dp[j] = max(dp[j] , dp[j-v[i]]+s[i]);}cout<< dp[w]<<endl;return 0; } 完全背包 優化

?

多重部分和問題 ?//多重背包

題意 :

　　有n中不同大小的數字ai，每種各mi個。判斷是否可以從這些數字之中選出若干使他們的大小恰好為K.

樣例 ： n = 3 ?a={3, 5, 8} ?m={3, 2, 2} K= 17

? ? ? ? 17 = 3*3 + 8?

思路：

　　dp[i+1][j] //用前i種數加和得到j時 第i種數最多剩余多少個

　　

　　　　　　　 ? ?m[i] ?, dp[i][j] >= 0 //說明前i個數已經可以等于j 了 不需要 第 i+1 個數

　　dp[i+1][ j ] =　-1 ， j < a[i] || dp[i+1][ j-a[i] ] <= 0,//?j < a[i] 目前還不是很懂這個條件?...dp[i+1][ j-a[i] ] <= 0 說明此時候沒法再用a[i]了

　　　　　　　　 dp[i+1][ j-a[i] ] -1，//和完全背包差不多， 如果此時a[i] 還存在 那么 就從 dp[i+1][ j-a[i] ] 去除1個a[i] 就可以得到..　　　　　　　　　　　?

#include <iostream> #include <cstdio> #include <string.h> using namespace std; const int mod = 1e9 + 7; const int maxn = 100000 + 5; const int INF = 0x3f3f3f3f; typedef long long LL;int n,k; int a[maxn] , m[maxn]; int dp[maxn];void solve() {memset(dp,-1,sizeof(dp));dp[0] = 0; //加和得到0 需要0個數字for(int i=0;i < n;i++){for(int j=0;j <= k;j++){if(dp[j] >= 0) dp[j] = m[i];else if(dp[ j-a[i] ] <= 0 || j < a[i] ){dp[j] = -1;}else{dp[j] = dp[ j-a[i] ] -1;}}}if(dp[k] >= 0) printf("Yes\n");else printf("No\n"); }int main() {cin >> n >> k;for(int i =0;i < n;i++){cin >> a[i] >> m[i];}solve ();return 0; } 多重部分和

?

// http://www.hankcs.com/program/cpp/poj-1742-coins.html

?

最長上升子序列 （LIS）

思路：做過好多次了 ?就是dp[i] 記錄的長度為 i + 1 的時候中末尾元素的最小值

//具體插入過程 看挑戰 P 66

#include <iostream> #include <cstdio>using namespace std; const int mod = 1e9 + 7; const int maxn = 10000 + 5; const int INF = 0x3f3f3f3f; typedef long long LL; int n; int s[maxn]; int dp[maxn]; void solve () {fill(dp,dp+n,INF);for(int i=0;i < n;i++){*lower_bound(dp,dp+n,s[i]) = s[i];//for(int j= 0;j < n;j++)// cout<< dp[j] <<" ";// cout<<endl; }printf("%d\n",lower_bound(dp,dp+n,INF) - dp); } int main() {cin >> n;for(int i=0;i < n;i++)cin >> s[i];solve ();return 0; } LIS

?

轉載于:https://www.cnblogs.com/Draymonder/p/7227276.html

總結

以上是生活随笔為你收集整理的dp问题 -挑战例题 2017-7-24的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。