USACO/inflate

来自NOCOW

这是USACO Chapter 3 .1中的OI题目Score Inflation的介绍及题解，参见翻译，C语言代码，C++语言代码，Pascal语言代码。

[编辑] 分析

类似无限背包问题的基础动态规划

普通的01背包，f[n,k]为前n个物品放前k单位空间价值

for i:=1 to n do
  for j:=k downto 1 do //防止重复

而本题因为每种有无限个，则为

for i:=1 to n do
  for j:=1 to k do

即可。

== 以上方程有误，按照这样推，就需要使用一维空间，f[v]表示在容量为V时可取的的最大价值 因为本题是完全背包所以伪代码应该是这样： ==

for i:=1 to n do
  for j:=0 to v do
    f[j]:=max(f[j],f[j-w[i]]+v[i]);

老大，上面的两个方程都是错的，里面的那个循环不应该从0，1开始，应该从这件物品的最小价值算起，要不然，数组越界啊！！！

(我和前面几个人没有联系)

一看就是完全背包.参见dd牛的背包9讲.

我的结果9#和8#用时1.2s多.

（我只和LS有关系）不加优化的完全背包果然会在最后的点TLE了

c[]：时间 w[]：分数 LSSS正解,要保证j-c[i]>=0

for (int i=1; i<=n; i++)
    for (int j=0; j<=v; j++)
        if (j-c[i]>=0 && f[j]<f[j-c[i]]+w[i])
            f[j] = f[j-c[i]]+w[i];

(我和LS的神牛们都没有联系) 实践证明不加任何优化的完全背包直接AC了...最大点0.594sec

依然与楼上无关。。 1.2s是因为用了max函数常数太大。。

加一个小优化可以快很多哦：就是在最外层物品的循环中加一个判断

for(i=0;i<n;i++){

   if(score[i] <= f[weight[i]])continue;
   ...

} 如果这样的话，说明就算加上这个物品也不会有任何改善，可以跳过该物品。

--chyx

对楼上的优化再优化一下预处理时，找出性价比最高的一组题 for i:=0 to m do f[i]:=i div weight[best]*score[best]; 比楼上少一个0.22的点

我可能和LS们有关系：裸的完全背包可以过，只不过别用max函数，调用函数果然耗时。直接

    f[0]:=0;
   for i:=n downto 1 do
     for j:=c[i] to m do
       if f[j]<f[j-c[i]]+w[i]
         then
           f[j]:=f[j-c[i]]+w[i];

即可。

我和LSS有关, 表示自己写一个max函数

inline int max(int a, int b) {
    return a > b ? a : b;
}

速度上基本就没有区别了.

这个问题不用这么纠结吧。。。很简单的一个完全背包，朴素可以直接过全点啊

     for(i=1;i<=n;i++)
      for(j=minutes[i];j<=m;j++)
        if(f[j]<f[j-minutes[i]]+points[i])
        f[j]=f[j-minutes[i]]+points[i];
    fprintf(fo,"%d\n",f[m]);

可在读入物品的时候进行优化，可以丢掉部分没用的（存在另一个物品体积是这个物品体积V的因数，而它体积扩大至V后对应价值大于此物体）

[编辑] 总结版

好了楼上不要吵了、这道题是背包问题没错. 而且是完全背包. 并不是1L说的01背包.

背包问题是求用容积为V的背包装物品所能获得的最大值.而01背包每种物品只能取一次的背包问题.完全背包则是每种物品无限取用（当然不能超过V）的背包问题..所以、这道题是完全背包问题

于是用m表示总体积. c[i]表示第i件物品的费用. v[i]表示第i件物品的价值.f[v]表示用v的容量所能得到的最大值、

则有以下状态转移方程

 for i:=1 to n do
   for j:=c[i] to m do
     f[j]:=max(f[j],f[j-c[i]]+v[i]);

最后输出f[m].

如果讲上述DP方程中j的循环顺序改成

 for j:=m downto c[i] do

就是01背包的状态转移方程了

[编辑] 优化

首先尽可能取比值最大的，然后换第二大的，只要一发现总值下降就不用再递归了，直接弹出

没懂LS说的总值是什么，按照DP公式：

 f[m] := max(f[j], f[j-c[i]]+v[i])

f[m]不会下降吧。

[编辑] 参考代码

[编辑] 引用

[1]

[2]