Question

对于杭电acm 3033 http://acm.hdu.edu.cn/showproblem.php?pid=3033 这个分组背包的至少怎么处理呀，详细

想了一天都没想出来，关键就是怎么让每组至少能取到一个
只求算法和思想，代码能在网上找到千万别复制代码

Answer 1

它要求的是每组物品至少选一个
这里我的办法可能有点啰嗦
令f[i][j]表示前i组中选择价钱为j的方案的最佳价值
则该状态满足最优子结构且无后效性 能想通就行了吧

初始化f[k][j]=-1(k!=0) 0(k==0) {因为这里初始化为-1 所以状态转移的时候只能从上个品牌转移过来 这样就达到至少选一个的效果了 不知道懂没有}
状态方程f[k][j]=maxx(f[k][j],f[k-1][j-w[i]]+v[i],f[k][j-w[i]]+v[i])
其中第i件物品属于第k组
解释起来也很简单
要么是上个品牌+该品牌 要么是该品牌选多个
这样就一定能保证每组都至少要选一个
因为除了f[0][i]其它都赋值的是-1，所以一定能够有前一组的转移过来 除非条件不够 就输出Impossible

输出Impossible还有个条件 就是组数的最大数还
这题我犯了个错误 对其理解还不是很透

追问

你这样初始化不行的，如果第二组能从第一组第一个转移后得到最大值，那么第一组所有数据就都没有意义了，那么也就是说第一中品牌商品一个都不会被选走。

Answer 2

把关键位置的代码复制下。。
for(i=1;i<=t;i++) //组数的循环。
{
if(num[i])
count++;
for(j=0;j<num[i];j++) //组数当中个数的循环，因为一组当中可以去多个，所以把j循环和K循环的位置颠倒下。
for(k=m;k>=0;k--) //背包容量的循环。
if(k>=vol[i][j])
{
dp[i][k]=Max(dp[i][k-vol[i][j]]+val[i][j] ,dp[i][k]); //先判断本组的。
dp[i][k]=Max(dp[i-1][k-vol[i][j]]+val[i][j] ,dp[i][k]); //在判断与前一组的。
}
}

追问

最好是带有为什么能达到这个效果的回答，昨天搜代码的时候看到另外一个人空间你也浏览过，也是分组背包，这种注释，我也能看出来的，真不求注释

追答

dp二位数组的初始为0。。
dp[i][k]=Max(dp[i][k-vol[i][j]]+val[i][j] ,dp[i][k]);
当遇到某组的第一件物品时，dp[i][k-vol[i][j]]+val[i][j]！=0。。dp[i][k]=0。。所以一定会去第一件物品。

追问

7 10 4
1 2 3
1 4 5
2 8 10
2 3 4
3 6 2
4 5 6
4 2 4

当我输入这组数据后，输出为10，明显每项的最小价值加一起也要13这就是用链接中的算法做
的，明显错误了http://hi.baidu.com/a363310925/blog/item/663fe94613672a3286947359.html

追答

可以这样写。。
if(dp[i][k-vol[i][j]]!=-INF && dp[i][k-vol[i][j]]+val[i][j]>dp[i][k])
dp[i][k]=dp[i][k-vol[i][j]]+val[i][j];
if(dp[i-1][k-vol[i][j]]!=-INF && dp[i-1][k-vol[i][j]]+val[i][j]>dp[i][k])
dp[i][k]=dp[i-1][k-vol[i][j]]+val[i][j];
把dp数组初始为INF(正无穷。) dp[0][0]=0;
这题的数据弱了。

追问

兄弟，你有qq没，以后有不会还想请教你，