背包类问题

01背包（ZeroOnePack）: 有N件物品和一个容量为V的背包。（每种物品均只有一件）第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。 完全背包(CompletePack): 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 多重背包(MultiplePack): 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 比较三个题目，会发现不同点在于每种背包的数量，01背包是每种只有一件，完全背包是每种无限件，而多重背包是每种有限件。

模板:

c是重量，w是价值，n是个数

void bag01(int c,int w)
{
    for(int i=v; i>=c; i--)
        dp[i]=max(dp[i],dp[i-c]+w);
}
void bagall(int c,int w)
{
    for(int i=c; i<=v; i++)
        dp[i]=max(dp[i],dp[i-c]+w);
}
void multbag(int c,int w,int n)
{
    if(c*n>=v)
    {
        bagall(c,w);
        return;
    }
    int k=1;
    while(k<=n)
    {
        bag01(k*c,k*w);
        n-=k;
        k*=2;
    }
    bag01(n*c,n*w);
}

用法:

先循环每一件物品的各个属性，最后dp[v]的值就是答案

以多重背包为例

const int N=50000+10;
int dp[N],v;
int num[N],weight[N],value[N];
void bag01(int c,int w)
{
    for(int i=v; i>=c; i--)
        dp[i]=max(dp[i],dp[i-c]+w);
}
void bagall(int c,int w)
{
    for(int i=c; i<=v; i++)
        dp[i]=max(dp[i],dp[i-c]+w);
}
void multbag(int c,int w,int n)
{
    if(c*n>=v)
    {
        bagall(c,w);
        return;
    }
    int k=1;
    while(k<=n)
    {
        bag01(k*c,k*w);
        n-=k;
        k*=2;
    }
    bag01(n*c,n*w);
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&v);
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d%d",&weight[i],&value[i],&num[i]);
    }
    for(int i=1; i<=n; i++)
        multbag(weight[i],value[i],num[i]);
    printf("%d\n",dp[v]);
    return 0;
}

zb的生日dp:

把一堆物品分成两堆，每个物品有自己的重量，最后使得两堆的差值最小.

//dp[v]:为其中一个人获得的重量，sum-dp[v]为另一个人重量,dp数组开的大一点
int sum = 0;
for (int i = 0; i < n; i++)
{
    scanf("%d", &a[i]);
    sum += a[i];
}
int v = sum / 2;
for (int i = 0; i < n; i++)
    for (int j = v; j >= a[i]; j--)
        dp[j] = max(dp[j], dp[j - a[i]] + a[i]);