完全背包--二维数组

完全背包问题是在01背包问题进行些改变，其大意为：
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
可以发现，它与01背包的区别在于这句话“每种物品都有无限件可用”，即对于特定容量，每件物品最多可放V/c[i]件，所以，将01背包的dp代码改为：

sum[i][j] = Max(sum[i - 1][j], sum[i - 1][j - k * c[i]] + k * v[i])

sum[i - 1][j - k * c[i]] + k * v[i]表示前i-1种物品中选取若干件物品放入剩余空间为j - k * c[i]的背包中所能得到的最大价值加上k件第i种物品,其中的k为选择i物品的数量;
于是，可以用三个循环完成这个步骤：

    for(i = 1;i <= n;i++)
        for(j = 1;j <= t;j++)
            for(k = 0;k * c[i] <= j;k++)
                sum[i][j] = Max(sum[i - 1][j], sum[i - 1][j - k * c[i]] + k * v[i]);

接下来可以做些简单的优化

设sum[i][j]表示出在前i种物品中选取若干件物品放入容量为j的背包所得的最大价值。那么对于第i种物品的出现，我们对第i种物品放不放入背包进行判断。
如果不放，那么sum[i][j]=sum[i-1][j]；
如果确定放，背包中应该已经出现了至少一件第i种物品，所以sum[i][j]中至少应该出现一件第i种物品,即sum[i][j]=sum[i][j-c[i]]+v[i]。
为什么会是sum[i][j-c[i]]+v[i]？
因为在前面已经最大限度的放了第i件物品,现在如果还能放，那就放这最后的一件,也可以理解为前面已经往背包中放入了第i件物品，每一次只增加一件的往背包里放,而且只能增加一件,多了放不下。
举个例子
有容量为5的背包，有三个物品：
物品a，价值为2，重量为1
物品b，价值为3，重量为2
物品c，价值为4，重量为5
再次拿出下图

1111.png

sum[i][j] = Max(sum[i - 1][j], sum[i][j - k * c[i]] + k * v[i])

完整代码如下：

#include <stdio.h>
int sum[1001][1001];//sum[i][j]放入第i个物品，j空间的背包最大重量
int Max(int a,int b);//判断大小
void init(int b);//初始化背包
void scok(int n,int t,int* c,int* v);//核心判断
int Max(int a,int b)
{
    if(a > b)
        return a;
    else
        return b;
}
void init(int b)
{
        for(int j = 0;j <= b;j++)
        {
            sum[0][j] = 0;
        }
}
void scok(int n,int t,int* c,int* v)
{
    int i,j;
    init(n);
    for(i = 1;i <= n;i++)
    {
        for(j = 1;j <= t;j++)
        {
            if(j >= c[i])
                sum[i][j] = Max(sum[i - 1][j], sum[i][j - c[i]] + v[i]);
            else
                sum[i][j] = sum[i - 1][j];
        }
    }
    printf("%d\n",sum[n][t]);
}
int main(){
    int n,t;
    int c[1003],v[1003];
    scanf("%d %d",&n,&t);
    for(int i = 1;i <= n;i++)
        scanf("%d %d",&c[i],&v[i]);
    scok(n, t, c, v);
    return 0;
}