/*
状态方程：f[i][j]=max{f[i-1][j],f[i-1][j-c[i]]+w[i]}
解释：对于这方方程其实并不难理解，方程之中，现在需要放置的是第i件物品，这件物品的体积是c[i],价值是w[i],因此f[i][j]代表第i件物品中假设背包总量为j（所以最后为啥结果是f[n][m]代表所有物品最大背包空间的结果），f[i-1][j]代表的就是不将这件物品放入背包，而f[i-1][j-c[i]]+w[i]则是代表将第i件放入背包之后的总价值，比较两者的价值，得出最大的价值存入现在的背包之中。
*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
const int MAXN = 1005;
int dp[MAXN]; // 滚动数组
int val[MAXN],weight[MAXN],num[MAXN]; // 价值 重量 个数
int n,m; // 物品种数 物品重量
// 状态转移方程：dp[i][j] = max( dp[i-1][j] , dp[i-1][ j - weight[i] ] + value[i] )
void ZeroOne_Pack(int val,int weight,int m) // 01背包
{
// 从1开始有讲究的，是因为涉及到dp[i-1][j],从0开始会越界
// for(int i=1; i<=n; i++) // 判断每个物品能否放进
// {
// // 这边两重for都可以倒着写，只是需要处理最边界的情况，滚动数组不一样
// for(int j=0; j<=m; j++) // 对每个状态进行判断
// {
// if(j>=weight[i]) // 能放进
// dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
//
// else dp[i][j]=dp[i-1][j]; // 不能放进
// }
// }
// 如果有需要可以还原以上注释的代码，具体情况具体分析
// 倒着 j-- 是因为当 i==2 时，j 从小到大递增的话，原来的数据可能就被新的数据覆盖掉
for(int j=m;j>=weight;j--) // 没有 j>=0 是因为 j>=weight[i] 代表能放进，放不进那就还是原来的值即可，没变过
// PS1：加判断状态是否可转移（dp[m]一定代表正好背包放满的状态的值）：因为for_j循环体内，每一种可能，都要经过判断，当前状态是否可转移，若可以，则调用max，否则跳过当前状态，进入下一种状态。
// PS2：不加判断状态是否可转移（dp[m]不一定代表正好背包放满的状态的值）：因为 j 代表每一种可能性，并不代表一个确定的使用空间的量，所以 dp[m] 到最后可能是一个虚值，但是如果dp初始化时，是个负大值（注意：这个负数要足够大，使虚值到达不了正数，否则会与真值混乱），dp[m] 最终且大于0，则该 dp[m] 是真实值。
// if(j==weight || dp[j-weight]!=0) // 这里0代表初始值
dp[j]=max(dp[j],dp[j-weight]+val); // j 代表使用了多少空间
}
// 状态转移方程：dp[i][j] = max ( dp[i-1][j - k*weight[i]] +k*value[i] ) （0<=k*weight[i]<=m）
void Complete_Pack(int val,int weight,int m) // 完全背包
{
// 如果有需要可以还原类似的以上注释的代码，具体情况具体分析
for(int j=weight;j<=m;j++)// 利用这种影响（因为物品不知道取几个，能取就减，这种影响正好就是这个题目的意思）
// if(j==weight || dp[j-weight]!=0) // 这里0代表初始值，其他同上
dp[j]=max(dp[j],dp[j-weight]+val);
}
// 把物品拆开，把相同的num[i]件物品 看成 价值跟重量相同的num[i]件不同的物品，那么，是不是就转化成了一个规模稍微大一点的01背包了
// for(int k=0; k<num[i]; k++) // 其实就是把这类物品展开，调用num[i]次01背包代码，三重 for 代码略（for_k 在 for_i 和 for_j 之间），不推荐
// dp[i][j] = max ( dp[i-1][j - k*weight[i]] +k*value[i] ) （0<=k<=num[i]）（这个跟完全背包差点就一毛一样了）
int Multi_Pack(int val[],int weight[],int n,int m) // 多重背包
{
mem(dp,0);
for(int i=0;i<n;i++) // 遍历每种物品
{
if(num[i]*weight[i]>m) // 如果全装进去已经超了重量，相当于这个物品就是无限的
{
Complete_Pack(val[i],weight[i],m); // 因为是取不光的。那么就用完全背包去套
}
else // 取得光的话，去遍历每种取法
{
// 三重 for 代码
// for(int i=1; i<=n; i++) // 每种物品
//
// for(int k=0; k<num[i]; k++) // 其实就是把这类物品展开，调用num[i]次01背包代码
//
// for(int j=m; j>=weight[i]; j--) // 正常的01背包代码
//
// dp[j]=max(dp[j],dp[j-weight[i]]+val[i]);
// 这里用到是二进制思想，降低了复杂度
// 为什么呢，因为他取的1,2,4,8...与余数个该物品，打包成一个大型的该物品
// 这样足够凑出了从[0,k) 个该物品取法
// 把复杂度从 k 变成了 logk
// 如k=11，则有1,2,4,4，足够凑出[0,11) 个该物品的取法
// i.e. k num
// 1 11
// 2 10
// 4 8
// 8 4
// 1 2 4 4
// 转换三重 for 代码，关键下面num[i]*val[i],num[i]*weight[i]这两个参数传参进去，dp[]在做 1+2+4+4 替换中间 for_k 循环 01 背包的操作
int k=1;
while(k<num[i])
{
ZeroOne_Pack(k*val[i],k*weight[i],m);
num[i]-=k;
k<<=1;
}
// 不需要 if num[i]>0 因为 <=0 都不会有误操作
ZeroOne_Pack(num[i]*val[i],num[i]*weight[i],m); // 为什么不用 k，因为要把剩余的 num[i] 最后走一遍01背包
}
}
return dp[m];
}
