-
01背包:
dp[i][j]取到第i个物品,背包容量为j情况下的最大价值 dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+v[i]); 从原来(i-1)的情况“腾”出来c[i]放i物品
-
完全背包:
dp[i][j]=max(dp[i-1][j],dp[i][j-c[i]]+v[i]); 从原来(i)的情况“腾”出来c[i]放i物品, 因为考虑放入一个物品 i 时应当考虑还可能继续放入i, 所以滚动数组时,01背包j逆序,完全背包正序。
具体什么作为j(背包容量)视具体情况而定。
Robberies 🤑
VJ链接:https://vjudge.net/problem/HDU-2955
这里注意要计算不被抓的最大概率
被抓的概率不满足乘法。
#include<map> #include<set> #include<queue> #include<cmath> #include<stack> #include<ctime> #include<cstdio> #include<vector> #include<string> #include<sstream> #include<cstdlib> #include<cstring> #include<cassert> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int MAXN=1e5+10; //#define pi acos(-1.0) #define INF 0x3f3f3f3f #define mod 1000000009 #define endll printf("\n") #define s1(a) scanf("%d",&a) #define lowbit(x) ((x)&(-x)) #define s2(a,b) scanf("%d %d",&a,&b) #define mem(a,b) memset(a,b,sizeof(a)) #define s3(a,b,c) scanf("%d %d %d",&a,&b,&c) int n,m; double p; int mi[111]; double pi[111]; double dp[MAXN];//到第i家银行获得j价值的最大不被抓率 //dp[i][j]=max(dp[i-1][j],dp[i-1][j-mi]+pi); int main() { int t;s1(t); while(t--) { scanf("%lf %d",&p,&n);m=0; for(int i=1;i<=n;i++) { scanf("%d %lf",&mi[i],&pi[i]); m+=mi[i]; } mem(dp,0);dp[0]=1;// for(int i=1;i<=n;i++) for(int j=m;j>=mi[i];j--) dp[j]=max(dp[j],dp[j-mi[i]]*(1-pi[i])); for(int i=m;i>=0;i--) { if((1-dp[i]) <= p) { printf("%d\n",i); break ; } } } return 0; }
-
多重背包
把以前缺的单调队列优化和多重背包可行性补了一下,以前感觉很头大的东西现在看也不是很难嘛
Coins (多重背包可行性)
VJ链接:https://vjudge.net/problem/POJ-1742
题意:给出n种硬币,和每种硬币的数量,求在价值1到价值m之间,这些硬币能凑出来的种类数。
思路:可以先只用第一种硬币,看看能凑出哪些价值。
然后在这些凑出的价值的基础上,用第二种硬币,得到用第一种和第二种能凑出的所有价值。直到求出用第一种到第n种得到的价值。
则在使用a[i]价值的硬币时,
如果j价值还没有被凑出来,且j-a[i]价值已经被凑出来,凑出j-a[i]时a[i]价值的硬币用量小于该硬币的总数量,
那么就可以在j-a[i]价值的基础上用一个a{i]价值的硬币,从而凑出j价值。
#include<cstdio> #include<string> #include<sstream> #include<cstdlib> #include<cstring> #include<cassert> #include<iostream> #include<algorithm> using namespace std; const int MAXN=1e5+10; #define s1(a) scanf("%d",&a) #define s2(a,b) scanf("%d %d",&a,&b) #define mem(a,b) memset(a,b,sizeof(a)) int n,m; int a[111],c[111]; //a价值,c数量 int use[MAXN];//凑出i价值对某物品使用数量 int dp[MAXN];//某价值能否凑成 int main() { while(~s2(n,m)&&(n+m)) { for(int i=1;i<=n;i++) s1(a[i]); for(int i=1;i<=n;i++) s1(c[i]); mem(dp,0); int ans=0;dp[0]=1; for(int i=1;i<=n;i++) { mem(use,0); for(int j=a[i];j<=m;j++) { if(!dp[j]&&dp[j-a[i]]&&use[j-a[i]]+1<=c[i]) { use[j]=use[j-a[i]]+1; dp[j]=1; ans++; } } } printf("%d\n",ans); } return 0; }