背包

练习

1. P1048 [NOIP2005 普及组] 采药

2. P1049 [NOIP2001 普及组] 装箱问题

3. P1060 [NOIP2006 普及组] 开心的金明

4. P1164 小A点菜

5. P1776 宝物筛选

6. P1616 疯狂的采药

7. P1510 精卫填海

8. P1504 积木城堡

9. P1679 神奇的四次方数

10. P2736 [USACO3.4]“破锣摇滚”乐队 Raucous Rockers

11. CF837D Round Subset

12. P1757 通天之分组背包

13. P1064 [NOIP2006 提高组] 金明的预算方案

01背包

普通版

#include<iostream>
using namespace std;

const int N = 105, M = 1005;
int v[N], w[N];
int dp[N][M];

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 = 1; j <= m; j++){
            if(j < v[i]) dp[i][j] = dp[i - 1][j]; 
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << dp[n][m];
    return 0;
}

​

普通版2压维压维优化（第二层循环和判断合并）

#include<iostream>
using namespace std;

const int N = 105, M = 1005;
int v[N], w[N];
int dp[N][M];

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 = 1; j <= m; j++){
            dp[i][j] = dp[i - 1][j]; 
            if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]); 
        }
    }
    cout << dp[n][m];
    return 0;
}

#include<iostream>
using namespace std;

const int N = 105, M = 1005;
int v[N], w[N];
int dp[M];

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 >= 1; j--){
            if(j >= v[i]) dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[m];
    return 0;
}

#include<iostream>
using namespace std;

const int N = 105, M = 1005;
int v[N], w[N];
int dp[M];

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];
    return 0;
}

P1048 [NOIP2005 普及组] 采药

#include<iostream>
using namespace std;

const int N = 105, T = 1005;
int ti[T];
int value[N];
int dp[N][T];
int t, m;

int main(){
    cin >> t >> m;
    for(int i = 1; i <= m; i++){
        cin >> ti[i] >> value[i];
    }
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= t; j++){
            if(j < ti[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - ti[i]] + value[i]);
        }
    }
    cout << dp[m][t];
    return 0;
}

P1164 小A点菜

#include<iostream>
#include<iomanip>
using namespace std;

const int N = 105, M = 1005;
int w[N];
int dp[N][M];

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

P1049 [NOIP2001 普及组] 装箱问题

dp表示最大占的空间（总 - max）dp表示最小剩余空间

#include<iostream>
using namespace std;

const int N = 35, M = 20005;
int v[N];
int dp[N][M];

int main(){
    int n, vv;
    cin >> vv >> n;
    for(int i = 1; i <= n; i++){
        cin >> v[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= vv; j++){
            if(j >= v[i]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + v[i]);
            else dp[i][j] = dp[i - 1][j];
        }
    }
    cout << vv - dp[n][vv];
    return 0;
}

#include<iostream>
#include<iomanip>
using namespace std;

const int N = 35, M = 20005;
int v[N];
int dp[N][M];

int main(){
    int n, vv;
    cin >> vv >> n;
    for(int i = 1; i <= n; i++){
        cin >> v[i];
    }
    for(int i = 1; i <= vv; i++){
        dp[0][i] = i;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= vv; j++){
            if(j >= v[i]) dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v[i]]);
            else dp[i][j] = dp[i - 1][j];
        }
    }
    cout << dp[n][vv];
    return 0;
}

P1060 [NOIP2006 普及组] 开心的金明

#include<iostream>
using namespace std;

const int N = 30005, M = 30;
int v[M], w[M];
int dp[M][N];
int n, m;

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

完全背包

普通普通版优化压维

 #include<iostream>
using namespace std;

const int M = 1e4 + 5, N = 1e4 + 5;
int v[N];
int w[N];
int dp[N][M];

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

#include<iostream>
using namespace std;

const int M = 1e7 + 5, N = 1e4 + 5;
int v[N];
int w[N];
int dp[N][M];

int main(){
    int n, m;
    cin >> m >> n;
    for(int i = 1; i <= n; i++){
        cin >> v[i] >> w[i];
    }
    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][j - v[i]] + w[i]);
            else dp[i][j] = dp[i - 1][j];               
        }
    }
    cout << dp[n][m];
    return 0;
}

#include<iostream>
using namespace std;

typedef long long ll;
const int M = 1e7 + 5, N = 1e4 + 5;
int v[N];
int w[N];
ll dp[M];

int main(){
    int n, m;
    cin >> m >> n;
    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];
    return 0;
}

多重背包

朴素做法

二进制优化