动态规划

神奇口袋问题

有一个神奇的口袋总的容积是 40，用这个口袋可以变出一些物品，这些物品的总体积必须是 40。

DP（动态规划）思路

k 种物品凑成体积 w 的方法：k-1 种物品凑成体积 w 的方法数加上 k-1 种物品凑成 w-a[k] 体积+k 物品 a[k] 这一种方法
Ways[w][k] = Ways[w][k] + Ways[w - a[k]][k - 1];

#include <cstring>
#include <iostream>

using namespace std;

int a[30]; int N;
int Ways[50][40]; //Ways[i][j] 表示从前 j 种物品里凑出体积 i 的方法数
int main()
{
 cin >> N;
 memset(Ways, 0, sizeof(Ways));//数组初始化值为 0
 for (int i = 1; i <= N; ++i)
 {
  cout << "请输入当前第" << i << "个商品的体积：" << endl;
  cin >> a[i]; //输入第 i 个商品的体积
  Ways[0][i] = 1;//边界条件 任意 i 个物品凑体积 0 的方法都是一种：选 0 个物品
 }
 Ways[0][0] = 1; //边界条件 0 个物品凑 0 体积方法只有一种：选 0 个物品
 for (int w = 1; w <= 40; ++w) {
  for (int k = 1; k <= N; ++k)
  {
   Ways[w][k] = Ways[w][k - 1];//令 k 种物品里凑出体积 w 的方法数，暂由前 k-1 个物品凑成。
   if (w - a[k] >= 0)         //如果第 k 种物品体积小于 w
    //则 k 种物品凑成体积 w 的方法：k-1 种物品凑成 w + k-1 种物品凑成 w-a[k] 体积+k 物品 a[k] 这一种方法
    Ways[w][k] = Ways[w][k] + Ways[w - a[k]][k - 1];
  }
 }
 cout << Ways[40][N];
 return 0;
}

0-1 背包问题

DP（动态规划）求解过程可以这样理解：对于前 i 件物品，背包容量为 j 时，所取得的最大价值（此时称为状态 3）只依赖于前两个状态。

状态 1：前 i-1 件物品，背包容量为 j。在该状态下，只要不选第 i 个物品，就可以转换到状态 3。

状态 2：前 i-1 件物品，背包容量为 j-w[i]。在该状态下，选完前 i-1 个商品后，背包还剩 w[i] 的容量，加上第 i 个物品，也可以转换到状态 3。

这里要求最大价值，所以只要从状态 1 和状态 2 中选择最大价值较大的一个即可。

`

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int maxn = 3500;
const int maxm = 13000;
int n, m;
int w[maxn], d[maxn];//w: 体积  d: 价值
////方法一： 二维数组表示
int dp[maxn][maxm]; //表示取 maxn 种物品，使它们总体积不超过 maxm 的最优取法取得的价值总和

int main() {
    cout << "物品个数 n:";
    cin >> n;
    cout << "背包的总容量体积：";
    cin >> m;
    for (int i = 1; i <= n; i++) {
        cout << "请输入物品" << i << "体积，单价：";
        cin >> w[i] >> d[i];
    }
    memset(dp, 0, sizeof(dp));//数组初始化值为 0
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (w[i] <= j)
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + d[i]);
            else dp[i][j] = dp[i - 1][j];
        }
    }
    cout << "最大价值：" << dp[n][m] << endl;
    return 0;
}

////方法二： 一维滚动数组
int dp[maxm];
int main()
{
    cout << "物品个数 n:";
    cin >> n;
    cout << "背包的总容量体积：";
    cin >> m;
    for (int i = 1; i <= n; i++)
    {
        cout << "请输入物品" << i << "体积，单价：";
        cin >> w[i] >> d[i];
    }
    memset(dp, 0, sizeof(dp)); //数组初始化 0

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

    cout << "最大价值：" << dp[m] << endl;
    return 0;
}