01背包

初始化的细节问题

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。

为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。

多重背包可以分成n个也可以用二进制来优化：

const int N=500+5;
const int M=10*N;
int dp[N];
int v[N];
int c[N];
int main()
{
    int n,m;//n为物品种数 m为容量
    RII(n,m);
    int cnt=0;
    rep(i,1,n)
    {
        int tempv,tempc,num;
        RIII(tempv,tempc,num);
        int c1=1;
        while(num-c1>0)
        {
            num-=c1;
            c[++cnt]=tempc*c1;
            v[cnt]=tempv*c1;
            c1*=2;
        }
        if(num)
        {
            c[++cnt]=tempc*num;
            v[cnt]=tempv*num;
        }
    }
    rep(i,1,cnt)
    repp(j,m,0)
    if(j>=v[i])
        dp[j]=max(dp[j],dp[j-v[i]]+c[i]);

    return 0;
}

View Code

打印物品：

要求逆序

 for(int i=n,j=m;i>=1;i--)
    if(bk[j][i])
    st.push(v[i]),j-=v[i];

View Code

有时：

m特变大时容易超时那么就应该转换元素进行dp

dp[i][j]代表前i个物品装上价值为j的东西后最小的重量

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define inf 0x3f3f3f3f
const int N=100+5;
int n,m,dp[N][N*N];
int v[N],w[N];
int main()
{
    RII(m,n);
    int sum=0;
    rep(i,1,n)
    RII(w[i],v[i]),sum+=v[i];
    CLR(dp,0x3f);

    rep(i,0,n)
    dp[i][0]=0;

    rep(i,1,n)
    rep(j,0,sum)
    if(j>=v[i])
    dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
    else
    dp[i][j]=dp[i-1][j];

    int ans=0;
    rep(i,0,sum)
    if(dp[n][i]<=m)ans=i;
    cout<<ans;

    return 0;
}

View Code

大牛总结的非常好：

https://www.kancloud.cn/kancloud/pack/70133