10
1 1 1 5 5 7 9 //体积
5 5 1 5 3 5 1//价值
01
完全
多重
分组
有依赖性
...
-----------------------------------------------------------------------------------------------------------------------------------------------------------------
01背包
vi ci
if (i+vi)
n 为物品数，m为背包容量
f[i][j]//表示在体积为j的情况下，装前i个物品时的最大价值。
那么在f[i-1][j]//取前i-1个物品的最大价值上考虑是否能放下第i的物品。
对于每一个物品，我们有两种选择，①是取，f[i][j]=f[i-1][j-v[i]]+c[i],②是不取 f[i][j]=f[i-1][j], 综上所述，f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+c[i]);
for (int i=1;i<=n;i++)
for (int j=m;j>0;j--)//思考，为什么是倒叙循环？
if (j>=v[i]) f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+c[i]);
else f[i][j]=f[i-1][j];
f[n][m]即为最优解。
优化 ：① 用滚动数组来求。
② 用一维优化。//观察动态规划方程，我们不难发现，f[i][j]只与上一层有关。
for (int i=1,i<=n;i++)
for (int j=v;j;j--)
f[j]=max(f[j];f[j-v[i]]+c[i]);
http://codevs.cn/problem/1068/
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
完全背包
vi ci
与01背包最大的区别 对于每一个物品来说，可以选无数次。
解答上次思考:
if 1->n
if vi==4, ci==4
f[4]==4; f[8]==f[4]+4;
也就是说 1->n, 对于一个物品，不止选一次。
也就是 完全背包。
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)//思考，为什么是倒叙循环？
if (j>=v[i]) f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+c[i]);
else f[i][j]=f[i-1][j];
同样 优化也有两种
① 用滚动数组来求。
② 用一维优化。
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
f[j]=max(f[j],f[j-v[i]]+c[i]);
http://acm.nyist.net/JudgeOnline/problem.php?pid=311
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
多重背包
也就是说限定物品选择的个数。
vi ci ki //对于第i个物品，体积为vi，价值ci，只能选择ki次。
① 将 ki 分为 ki 个物品，然后用01背包解决。
代码：
for (int i=1;i<=n;i++)
{
scanf("%d%d%d",&v,&c,&k);
for (int j=1;j<=k;j++)
s[++cnt].v=v,s[cnt].c=c;
}
② 采用类似lca的方法，将k个物品分为 1,2,4,8,16，..... 2^n.
这样对于每一个自然数i都可以被组合出来。然后再采用01背包。
代码：
while (n--) //接下来输入n中这个物品
{
scanf("%d%d%d", &vi, &ci, &ki); //输入每种物品的数目和价值
for (int k=1; k<=ki; k<<=1) //<<右移 相当于乘二
{
value[cnt]=k*vi;//体积
size[cnt++]=k*ci;//价值
ki-=k;
}
if (ki>0)
{
value[cnt]=ki*vi;
size[cnt++]=ki*ci;
}
}
http://codevs.cn/problem/3269/
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
分组背包
vi ci ki //对于i的物品，体积为vi,价值为ci,属于第ki个分组，对于每一个分组而言，最多选一件。
for k=1->K
for j=M->0
for i=1->s[k]//当前分组中的所有元素
f[j]=max(f[j],f[j-v[i]]+v[i]);
ps:注意三层循环的顺序，for j=m->0 必须在 for i=1->s[k] 之外，这样才能保证每一个分组最多只会选1个物品。
http://acm.hdu.edu.cn/showproblem.php?pid=1712
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
有依赖性背包
直接上例题
http://codevs.cn/problem/1155/
预处理分组，然后上分组背包。
说实话，这种题不难，但预处理很恶心。
begin
read(m,n);
j:=0;
for i:=1 to n do
begin
read(x1,y1,z1);
if z1=0 then begin inc(j); inc(s[j,0].x); s[j,s[j,0].x].x:=x1; s[j,s[j,0].x].y:=x1*y1; s[j,0].y:=i; end
else
begin
for k:=1 to j do
if z1=s[k,0].y then
begin
z:=s[k,0].x;
for l:=1 to z do
begin
inc(s[k,0].x);
s[k,s[k,0].x].x:=s[k,l].x+x1;
s[k,s[k,0].x].y:=s[k,l].y+x1*y1;
end;
end;
end;
end;
s[0,0].x:=j;
end;
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
背包问题的扩展
多米诺骨牌
多米诺骨牌有上下2个方块组成，每个方块中有1~6个点。现有排成行的
上方块中点数之和记为S1，下方块中点数之和记为S2，它们的差为|S1-S2|。例如在图8-1中，S1=6+1+1+1=9，S2=1+5+3+2=11，|S1-S2|=2。每个多米诺骨牌可以旋转180°，使得上下两个方块互换位置。
编程用最少的旋转次数使多米诺骨牌上下2行点数之差达到最小。
对于图中的例子，只要将最后一个多米诺骨牌旋转180°，可使上下2行点数之差为0。
输入输出格式 Input/output
输入格式：
输入文件的第一行是一个正整数n(1≤n≤1000)，表示多米诺骨牌数。接下来的n行表示n个多米诺骨牌的点数。每行有两个用空格隔开的正整数，表示多米诺骨牌上下方块中的点数a和b，且1≤a，b≤6。
输出格式：
输出文件仅一行，包含一个整数。表示求得的最小旋转次数。
题解 ：
f[i][j]//表示前i个骨牌，点数相差j的翻动次数。
动态转移方程：
int cha=a[i]-c[i];
for i=2->n
for j=-5000->5000
f[i][j]=min(f[i][j],min(f[i-1][j-a[i]],f[i-1][j+a[i]]+1));
--------------------------------------------------------------------------------------------------------------------------------------------------------------------