題意：bool多重背包
分析：學了種很快的新方法，就是每次填f[j]時直接由f[j-weight[i]]推出，前提是num[j - weight[i]]<sum[i]num每填一行都要清零，num[j]表示目前物品填充j大小的包需要至少使用多少個
但是使用這種方法有一個條件，就是要求f數組隻能是bool類型。否則會出錯。
對于bool型則不會有成本效益的問題，隻有體積可達和不可達的問題，在可達前提下隻要盡量少的使用目前物品即可，value型則不行，可達不一定少用目前物品，因為多用目前物品可能會獲得高價值。 例如，如果目前物品成本效益極高，那麼對于任意大小的包都應該盡量多的目前物品以追求高價值，用上述方法會使得後面包容量足夠大時，會有些位置（j=(sum[i]+1)*weight[i]）因無法滿足條件num[j - weight[i]]<sum[i]（即之前已經把目前物品買完），而無法購買目前物品。
View Code #include < iostream >
#include < cstdio >
#include < cstdlib >
#include < cstring >
using namespace std;
#define maxn 105
#define maxm 100005
bool f[maxm];
int used[maxm], num[maxn], value[maxn];
int n, m;
void input()
{
for ( int i = 0 ; i < n; i ++ )
scanf( " %d " , & value[i]);
for ( int i = 0 ; i < n; i ++ )
scanf( " %d " , & num[i]);
}
void work()
{
memset(f, 0 , sizeof (f));
f[ 0 ] = true ;
int sum = 0 ;
for ( int i = 0 ; i < n; i ++ )
{
memset(used, 0 , sizeof (used));
for ( int j = value[i]; j <= m; j ++ )
if ( ! f[j] && f[j - value[i]] && used[j - value[i]] < num[i])
{
f[j] = true ;
used[j] = used[j - value[i]] + 1 ;
sum ++ ;
}
}
printf( " %d\n " , sum);
}
int main()
{
// freopen("t.txt", "r", stdin);
while (scanf( " %d%d " , & n, & m), n | m)
{
input();
work();
}
return 0 ;
}