题意：
在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]; else dp[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; }
下面是优化过内存的
#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; }
完全背包
题意：
在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]; else dp[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 "); else printf("No "); } 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 ",lower_bound(dp,dp+n,INF) - dp); } int main() { cin >> n; for(int i=0;i < n;i++) cin >> s[i]; solve (); return 0; }