题解 SP39 【PIGBANK - Piggy-Bank】

· · 题解

洛谷SP39 存钱罐（Piggy-bank）

一 题目描述

给定N个商品、背包总体积为W和每个商品的价值与体积，每个商品可以用无限次，请求出当商品恰巧装满背包时价值的最小值

数据范围

1<=E(空背包体积)<=F(满背包体积)，N(商品数量)<=500，P(每个商品的价值)<=50000，W(每个商品的体积)<=10000

详细题目描述见洛谷SP39

http://www.luogu.com.cn/problem/SP39

二 算法分析

根据题意得：采用动态规划算法，属于背包——完全重复背包

状态定义：f(i,j)表示1~i种商品花费j的体积所得的最优值（最小值）

所求：f(N,F-E)即为所求（N为商品总数，F-E为商品总体积）

转移方程：

f(i,j)= \begin{cases} 0 & j==0\\ -100 & i==0\\ min_{k=0}^{j/a[i].v} f(i-1,j-k*a[i].v)+k*a[i].f & j>k*a[i].v\\ \end{cases}

一点小事情：建议最好预处理一下背包体积m=F-E

一 递归实现

递归很简单，直接照抄方程就行了

void f(int i,int j){
  if(j==0){
    data[i][j]=0;//填表
    return ;//注意这里不要多东西，函数类型为void型
  }
  if(i==0){
    data[i][j]=-100//不合法状态
    return ;
  }
  int mink=0x3f3f3f3f;//初值大一点
  for(int k=0;k<=j/a[i].v;++k){
    if(j>k*a[i].v) if(data[i-1][j-k*a[i].v]==-1) f(i-1,j-k*a[i].v);
    if(data[i-1][j-k*a[i].v]+k*a[i].f<mink) mink=data[i-1][j-k*a[i].v]+k*a[i].f;//照抄方程
  }
  data[i][j]=mink;//别忘了最后把答案记录下来
}

递归实现

1 初始化

根据递归data表格可知第一行赋初值为无穷大，data[0][0]=0;

    for(int i=1;i<=w;i++) f1[i]=0x3f3f3f3f;
    f1[0] = 0;

2 顺序求解

照抄转移方程第三行，代码略

3 答案

输出data[n][m]即可

滚动实现

开两个一维数组data[M]与data1[M],每次做完data数组之后填入data1，如此交替往复求解

代码实现类似于递推求解

    for(int i=1;i<=n;i++){
        for(int j=1;j<=w;j++){
            long long min1 = 0x3f3f3f3f;
            int x;
            int g = j/a[i].w;
            for(int k=0;k<=g;k++) 
                if(min1>f1[j-k*a[i].w]+k*a[i].v) 
                    min1 = f1[j-k*a[i].w] + k*a[i].v,x=k;
            f[j] = min1;
        }
        for(int j=1;j<=w;j++) f1[j] = f[j];
    }

降维实现

注意好求解次序，每次利用已求过的值求解接下来的值

        for(int i=1;i<=n;i++){
            for(int j=cost[i];j<=m;j++){
                f[j]=min1(f[j],f[j-cost[i]]+val[i]);
            }
        }

END

BY FNOI_ZRH0301