0-1背包再谈

搞了两天的DP了，对01背包又有了新的理解。网上有很多资料，可能都比我写的好，只是记录一下我的理解。

代码编译过不了，只是记录背包问题的思想。

参考：《算法入门经典》

首先一个引例：

物品无限的背包问题——DAG 硬币问题

就是加了一个权值的DAG，ans = max(ans,dp(C-V[i])+W[i]);

由于01背包问题，按照DAG模型的话，不能表示每个物品是否拿过，这要求我们决策有序化。

决策的分层阶段，d(i,j)当前阶段是 i ，背包容量是 j ，

边界条件：

d(i,j) = 0; i>n;

答案 d(1,C);

状态转移方程：

d(i,j) = max(d(i+1,j),d(i+1,j-v[i])+w[i]);

还有一种就是对称的定义：

前1~i个物品都放入时背包容量为j 是的最优值。

f(i,j) = max(f(i-1,j),f(i-1,j-v[i])+w[i]);

答案是 f(n,C);

然后就是滚动数组了：

这里的DP顺序很有讲究。

f是从上到下，从右到左的递推的。

计算f(i,j)时，f[j]保存的是f(i-1,j)的值，f[j-v] 保存的是 f(i-1,j-v)的值。

这样状态转移方程就出来了：

f[j] = max(f[j],f[j-v]+w);

#include <bits/stdc++.h>
using namespace std;

#define num 2000
#define C 100000

int d[num][C];
int n;  //物品种量

///物品无限 —— DAG 硬币问题

int d[C];
bool vis[C];
int dp(int C) {
    if(vis[C]) return d[C];
    vis[C] = 1;
    int& ans = d[C];
    ans = -(1<<30);
    for(int i=1;i<=n;i++) {
        if(C>V[i]) {
            ans = max(ans,dp(C-V[i])+W[i]);
        }
    }
}

int main()
{
    ///边界是d[i][j] = 0; i>n
    ///i~~n都放到背包里面去
    ///答案d[1][C];

    for(int i=n;i>=1;i--) {
        for(int j=0;j<=C;j++) {
            d[i][j] = (i==n? 0 : d[i+1][j]);
            if(j>=V[i]) d[i][j] = max(d[i][j],d[i+1][j-V[i]]+W[i]);
        }
    }
    
    ///规划方向
    ///对称定义
    ///把1~i放到背包里面去
    for(int i=1;i<=n;i++) {
        for(int j=0;j<=C;j++) {
            f[i][j] = (i==1? 0: f[i-1][j]);
            if(j>=V[i]) f[i][j] = max(f[i][j],f[i-1][j-V[i]]+W[i]);
        }
    }
    
    
    ///滚动数组
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++) {
        scanf("%d%d",&V,&W);
        for(int j=C;j>=0;j--) {
            if(j>=V) {
                f[j] = max(f[j],f[j-V]+W);
            }
        }
    }
    
    return 0;
}