背包问题答题模板

0-1背包

每件商品只能拿一件或者不拿。

// 假设
int m; // 背包容量
int n; // 商品数量
int v[n]; // 商品的价值列表
int w[n]; // 商品的重量（cost）列表
int dp[n][m];

朴素二维数组方式

for （int i=1; i<=n; i++）{
  for (int j=1; j<=m; j++) {
    if (j>=v[i])
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
    dp[i][j] = dp[i-1][j];
  }
}
return dp[m]; // dp数组的最后一个元素即为最优解。

滚动数组方式优化

for (int i=1; i<=n; i++) {
  for (int j=m; j>=w[i]; j--) {
    dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
  }
}

一个AC的例程

#include <iostream>

using  namespace std;

int v[1005];
int w[1005];

int dp[1005];

int main()
{
    int n,m;
    cin>>n>>m;
    for (int i=1; i<=n; i++)
        cin>>v[i]>>w[i];
        
    for (int i=1; i<=n; i++) {
        for (int j=m; j>=v[i]; j--) {
                dp[j] = max(dp[j], dp[j-v[i]]+w[i]);
        }
    }        

    cout<<dp[m]<<endl;
    return 0;
}

关于dp数组的初始化

要求恰好装满背包时，初始时dp[0]=0，其他的dp[1...m]=负无穷。这样就可以保证最终得到的dp[m]是一种恰好装满背包的最优解。

如果没有恰好装满背包的要求而只是希望价格尽量大时，初始化时应该将dp[0...m]=0。

初始化时dp数组就是在没有任何物品放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可以在什么都不装且价值为0的情况下被"恰好装满"，其他容量的背包均没有合法的解，属于未定义的状态，应该被赋值为负无穷。
如果背包并非必须装满，那么任何容量的背包都有一个合法解”什么都不装“，这个解的价值为0，所以初始时状态的值也就全部为0.

完全背包

每件商品可以拿无数件。

滚动数组

for (int i=1; i<=n; i++) {
  for (int j=m; j>=w[i]; j--) {
    for (int k=0; k*w[i]<=j; k++)
    	dp[j] = max(dp[j], dp[j-k*w[i]]+k*v[i]);
  }
}

优化

for (int i=1; i<=n; i++) {
  for (int j=w[i]; j<=m; j++) { // 放一件之后 还能放下 就继续放
    dp[j] = max(dp[j], dp[j-w[i]]+v[i]); 
  }
}

一个AC的例程。

#include <iostream>

using namespace std;

int dp[1005];

int main()
{
    int n,m;
    cin>>n>>m;
    int v[1005];
    int w[1005];
    
    for (int i=1; i<=n; i++) 
        cin>>v[i]>>w[i];
        
    for (int i=1; i<n; i++) {
        for (int j=v[i]; j<=m; j++) {
            dp[j] = max(dp[j], dp[j-v[i]]+w[i]);
        }
    }
    cout<<dp[m]<<endl;
    
    return 0;
}

多重背包

每件物品只能拿固定次。

朴素做法

for (int i=1; i<=n; i++) {
  for (int j=m; j>=0; j--) {
    for (int k=1; k<=s[i] && k*w[i]<=j; k++) { // s[i] 指第i件商品一共有多少件
      dp[j] = max(dp[j], dp[j-k*w[i]]+k*v[i]);
    }
  }
}

一个AC的例程。

#include <iostream>

using namespace std;

int dp[1005];

int main()
{
    int n,m;
    cin>>n>>m;
    
    int v[1005];
    int w[1005];
    int c[1005];
    
    for (int i=1; i<=n; i++) {
        cin>>v[i]>>w[i]>>c[i];
    }
    
    for (int i=1; i<=n; i++) {
        for (int j=m; j>=v[i]; j--) {
            for (int k=1; k<=c[i] && k*v[i]<=j; k++) {
                dp[j] = max(dp[j], dp[j-v[i]*k]+w[i]*k);
            }
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}

二进制优化

另一种优化

这两种优化方式暂时没弄懂

混合背包

二维费用的背包问题

int n; // 商品数目
int v; // 约束1
int m; // 约束2

int c_v[n]; // 约束1的cost
int c_m[n]; // 约束2的cost

for (int i=1; i<=n; i++) {
  for (int j=v; j>=c_v[i]; j--) {
    for (int k=m; k>=c_m[i]; k--) {
      f[j][k] = max(f[j][k], f[j-c_v[i]][l-v_m[i]]+c);
    }
  }
}

下边是一道题的AC代码

#include <iostream>
using namespace std;

int v_v[1005];
int v_m[1005];
int w[1005];

int dp[1005][1005];

int main()
{
    int n, v, m;
    cin>>n>>v>>m;
    
    for (int i=1; i<=n; i++) {
        cin>>v_v[i]>>v_m[i]>>w[i];
    }
    
    for (int i=1; i<=n; i++) {
        for (int j=v; j>=v_v[i]; j--) {
            for (int k=m; k>=v_m[i]; k--) {
                dp[j][k] = max(dp[j][k], dp[j-v_v[i]][k-v_m[i]]+w[i]);
            }
        }
    }
    cout<<dp[v][m]<<endl;
    return 0;
}