• 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;
}