Codeforces Gym-102219 2019 ICPC Malaysia National E. Optimal Slots(01背包+输出路径)

Codeforces Gym-102219 2019 ICPC Malaysia National E. Optimal Slots(01背包+输出路径)

  • 题意:给你一个体积为\(T\)的背包,有\(n\)个物品,每个物品的价值和体积都是是\(a_{i}\),求放哪几个物品使得总价值最大,输出它们,并且输出价值的最大值.

  • 题解:其实就是一个01背包输出路径的裸题,直接上板子就行了.(一维的背包写法其实还是不太怎么怎么理解,具体的以后再补).

  • 代码:

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <stack>
    #include <queue>
    #include <vector>
    #include <map>
    #include <set>
    #include <unordered_set>
    #include <unordered_map>
    #define ll long long
    #define fi first
    #define se second
    #define pb push_back
    #define me memset
    const int N = 1e6 + 10;
    const int mod = 1e9 + 7;
    using namespace std;
    typedef pair<int,int> PII;
    typedef pair<long,long> PLL; int t;
    int a[N];
    int dp[N];
    int n;
    int p[2000][2000];
    int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    while(cin>>t){
    me(dp,0,sizeof(dp));
    me(p,0,sizeof(p));
    if(t==0) return 0;
    cin>>n;
    for(int i=1;i<=n;++i){
    cin>>a[i];
    } for(int i=n;i>=1;--i){
    for(int j=t;j>=a[i];--j){
    if(dp[j-a[i]]+a[i]>=dp[j]){
    dp[j]=dp[j-a[i]]+a[i];
    p[i][j]=1;
    }
    }
    }
    int j=t;
    for(int i=1;i<=n;++i){
    if(p[i][j]){
    printf("%d ",a[i]);
    j-=a[i];
    }
    }
    printf("%d\n",dp[t]);
    } return 0;
    }
上一篇:HAProxy+keepalived+MySQL 实现MHA中slave集群负载均衡的高可用


下一篇:[IOS]Setting Bundle + StoryBoard