01背包

朴素

NOIPJ2001D 装箱问题

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 35;
int n, v, a[N];
int dp[N][20005];
int f[20005];
int main(void)
{
    cin >> v >> n;
    for(int i = 1; i <= n ;i ++) cin >> a[i];
    for(int i = 1; i <= n; i++)
    {
        for(int j = v; j >= a[i]; j--)
        // for(int j = 0; j <= v; j++)
        {
            f[j] = max(f[j], f[j - a[i]] + a[i]);
            // dp[i][j] = dp[i - 1][j];
            // if(j >= a[i])
            //     dp[i][j] = max(dp[i][j], dp[i- 1][j - a[i]] + a[i]);
        }
    }
    cout << v - f[v];
    return 0;
}

空间压缩

j逆向

开心的金明 - whoj

/* created by chjshen, date: 2024-03-16 01:33 */
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 25, M = 3E4 + 5;
int n, m, v[N], p[N], c[N];
int dp[M];
void handle(void)
{
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= v[i]; j--)
        {
            dp[j] = max(dp[j], dp[j - v[i]] + c[i]);
        }
    cout << dp[m];
}
void initInput(void)
{
    ios::sync_with_stdio(0);
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i] >> p[i];
        c[i] = v[i] * p[i];
    }
}
int main(void)
{
    initInput();
    handle();
    return 0;
}

完全背包

朴素

YBTJ1268 【例9.12】完全背包问题

空间压缩

j正向

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 35, M = 300;
int n, m, w[N], c[N];
int dp[N][M];
void dp1()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= m; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if(j >= w[i]) dp[i][j] = max(dp[i][j], dp[i][j - w[i]] +  c[i]);
            // for(int k = 1; k <= j / w[i]; k++)
            // {
            //     dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * c[i]);
            // }
        }
    }
    cout << "max=" << dp[n][m];
}
int f[M];
void dp2()
{
     for(int i = 1; i <= n; i++)
    {
        for(int j = w[i]; j <= m; j++)
        {
           f[j] = max(f[j], f[j - w[i]] +  c[i]);
            
        }
    }
    cout << "max=" << f[m];
}
int main(void)
{
    cin >> m >> n;
    for(int i = 1; i <= n; i++) cin >> w[i] >> c[i];
    // dp1();
    dp2();
    return 0;
}

最小/少问题

C - Strange Bank - whoj

/* created by chjshen, date: 2024-03-15 14:18 */
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e6 + 5;
int n;
int cnt;
int dp[N];
int a[N];
void handle(void)
{
    for (int i = 1; i <= cnt; i++)
    {
        for (int j = a[i]; j <= n; j++)
        {
            dp[j] = min(dp[j], dp[j - a[i]] + 1);
        }
    }
    cout << dp[n];
}
void initInput(void)
{
    ios::sync_with_stdio(0);
    cin >> n;
    cnt = 1, a[1] = 1;
    int six = 1, nine = 1;
    while (six <= n)
    {
        six *= 6;
        if (six <= n) a[++cnt] = six;
    }
    while(nine <= n)
    {
        nine *= 9;
        a[++cnt] = nine;
    }
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
}
int main(void)
{
    initInput();
    handle();
    return 0;
}

多重背包

转换成01背包来解决，二进制拆分优化

B - Factorial Yen Coin - whoj

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 101, M = 1e7 + 5;
int n = 10;
int m, a[N],cnt, c[N];
int dp[M];
int main(void)
{
    cin >> m;
    a[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        a[i] = a[i - 1] * i;
    }
    cnt = n;
    for(int i = 1; i <= n; i++)
    {
        c[i] = 1;
        int p = 2, q = 100;
        while(p <= q)
        {
            q -= p;
            a[++cnt] = p * a[i];
            c[cnt] = p;
            p *= 2;
        }
        if(q)
            a[++cnt] = a[i] * q, c[cnt] = q;
    }
    memset(dp, 0x3f, sizeof dp);
     dp[0] = 0;
     
    for(int i = 1; i <= cnt; i++)
    {
        for(int j = m; j >= a[i]; j--)
        {
          dp[j] = min(dp[j], dp[j - a[i]] + c[i]);
        }
    }
    cout << dp[m];
    return 0;
}

恰好问题

背包与方案数

SFJSJJZN3141 数字组合

ac代码：

/* created by chjshen, date: 2024-03-17 09:53 */
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 105;
const int M = 1e4 + 5;
int a[N], n, m;
int dp[M];
void handle(void)
{
   dp[0] = 1;
   for (int i = 1; i <= n; i++)
   {
       for (int j = m; j >= a[i]; j--)
       {
           dp[j] = dp[j] + dp[j - a[i]];
       }
   }
   cout << dp[m] << endl;
}
void initInput(void)
{
   ios::sync_with_stdio(0);
   cin >> n;
   cin >> m;
   for (int i = 1; i <= n; i++)
   {
       cin >> a[i];
   }
}
int main(void)
{
   initInput();
   handle();
   return 0;
}

NOIPS2018B货币系统

分组背包

和01背包几乎一样，多一层循环一个组的物品。

混合背包

想各种办法转换成01背包：多重转01背包的思路，完全背包也可以转成01背包。

二维费用背包

多一维即可，dp[i][j][k] 表示前i个物品放入容量（第一维）为j，重量（另一维）为k的背包中的最大值。