部分背包问题的补充

关于部分背包问题，之前我们已经阐述了O(nlog2n)的算法。但是我们要注意，这是建立在背包不一定需要装满的情况下，若是背包一定需要恰好装满，那么会怎么样呢？两者之间有什么不同呢？

这有着本质上的不同。

部分背包：f[i] 两种要求（不同题目）：

重量<=i的最优值

重量==i的最优值

如图（若物品大小，价值均为5）：

他不见了。

事实上，对于每一格,存放的是当前容量,可放置的最大价值.若是存放当前容量,恰好放置的最大价值。如图：

他不见了。

假设我们每一个都初始化为-1，充当着哨兵，表示没有存放任何东西（第0位要改为0，因为接下来才可以放东西）。背包DP时，我们i从总容量load-w扫描0（倒着），判断当前的容量是否为-1，不是，那么F[i+w]才可以进行状态转移。

程序如下：

#include <fstream>
using namespace std;

ifstream fin("Pack_part_fill-up.in");
ofstream fout("Pack_part_fill-up.out");

#define maxn 1000
#define maxload 10000

int w[maxn],v[maxn],t[maxn],n,load;
int F[maxload];

int main() {
    fin >> n >> load;
    for (int i=0; i!=n; ++i)
        fin >> w[i] >> v[i] >> t[i];//读入

    memset(F,-1,sizeof(F));//整个数组清为-1
    F[0]=0;//但是第0位要为0
    for (int i=0; i!=n; ++i) {
        int P=1;
        for (;((P<<1)<=t[i]);P<<=1) //二进制捆绑
            for (int j=load-P*w[i]; j>=0; --j)//倒着的
                if (F[j]!=-1)//当前容量不为-1才行
                    F[j+P*w[i]]=max(F[j]+P*v[i],F[j+P*w[i]]);
                   
        P=t[i]-(P>>1);
        if (P==0) continue;
        
        for (int j=load-P*w[i]; j>=0; --j)
            if (F[j]!=-1)
                F[j+P*w[i]]=max(F[j]+P*v[i],F[j+P*w[i]]);
    }

    fout << F[load];//最后直接输出F[load]，不用找最大了
    return 0;
}