背包问题

1. 01背包

状态说明：背包体积为v，物品个数为n，f[n,v]表示前n件物品加入背包的最大价值。c_i,w_i表示物品i的体积和价值。
对于第i件物品，有两种选择，加入或不加入，状态转移方程为：
f[i,v]=max(f[i-1,v], f[i-1,v-c_i]+w_i)
空间优化：若用二维数组，需要(n+1)*(v+1)的空间，这里采用滚动数组，需要(v+1)的空间。
步骤：
1 初始化数组：
f[v+1]={0,0,0,0,0,...} 不要求装满
f[v+1]={0,-INF,-INF,-INF,...} 要求装满
2 遍历更新

for(i=0;i<n;i++)  //遍历每件物品
  for(j=v;j>=c_i;j--)  //采用滚动数组，所以从后往前赋值；遍历背包的容量，到c_i时就可以，因为再小背包装不下了物品i，f[i,v]=f[i-1,v],不必更新
    f[j]=max(f[j], f[j-c_i]+w_i); //采用滚动数组，所以从后往前赋值

3 返回结果f[v]。有的题目求的是最小价值，max换成min即可。有时题目隐含的给出物品的价值，例如物品的个数作为价值，求个数最小。

2. 完全背包

即每件物品可以选无穷件。01背包只有一件，所以状态转移时为：max(选0件，选1件)。这里状态转移时，需要一个for循环，遍历所有可能的件数，再进行一次状态转移。
时间优化
对背包体积遍历时，从前往后遍历

for(i=0;i<n;i++)  
  for(j=c_i;j<=v;j++)  //从前往后遍历背包体积
    f[j]=max(f[j], f[j-c_i]+w_i); 

例1 零钱兑换

背包体积为总金额，物品为不同面额的硬币，物品价值为硬币个数，求最小价值，完全背包。

    int coinChange(vector<int>& coins, int amount) {
        int len=coins.size();
        if(amount==0 || len==0) return 0;

        int INF=1000000;
        vector<int> dp(amount+1,INF);
        dp[0]=0;

        for(int i=0;i<len;i++){
          for(int j=coins[i];j<=amount;j++){
            dp[j]=min(dp[j],dp[j-coins[i]]+1);
          }
        }

        if(dp[amount]>=INF)
          return -1;
        else
          return dp[amount];
    }

例2 完美平方

背包容量为n，物品为小于n的平方数，数字的个数为价值，求最小，完全背包。

    int numSquares(int n) {
        if(n<=0) return 0;

        const int INF = 1000000;
        vector<int> dp(n+1,INF);
        dp[0]=0;

        int len=sqrt(n);
        vector<int> v; //物品
        for(int i=1;i<=len;i++)
            v.push_back(i*i);

        for(int i=0;i<len;i++){ //遍历len件物品
            for(int j=v[i];j<=n;j++){ //遍历不同体积的背包
                dp[j]=min(dp[j],dp[j-v[i]]+1);
            }
        }

        return dp[n];
    }