coding

1.如此编码

纯数学模拟。

#include<iostream>
#include<vector>

using namespace std;

int main(){
    int n , m ;
    vector<int> a(n+1),b(n+1) ;
    vector<long> c(n+1);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    c[0] = 1 ;
    long long flag = 1 ;
    for(int i=1;i<=n;i++){
        c[i]=flag*a[i];
        flag = c[i];
    }
    for(int i=n;i>=1;i--){
        b[i]=m/c[i-1];
        m = m%c[i-1];
    }
    for(int i=1;i<=n;i++){
        cout<<b[i]<<" ";
    }
    return 0 ;
}

2.何以包邮？

本质是稍作改动的 01背包问题 ，先复习~~（预习）~~下。

背包基础

有件物品和一个容量为的背包。放入第i 件物品花费的费用是，得到的价值是，求将哪些物品装入背包可使价值总和最大。（这里的费用可理解为将某个物品装入背包所付出的空间上的代价，可视作cost，可视作worth，下面的代码统一用这两个变量表示费用和价值）

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：表示前件物品恰放入一个容量为的背包可获得的最大价值。实际上不需要正好装满，初始化可以分开这两种情况，如下是状态转移方程：

$f[i][j]=max(f[i−1][j],f[i−1][j−c[i]]+w[i])$

如果不放第件物品，问题转化为前件物品放入容量为的背包中，最大价值为；

如果放第件物品，问题转化为前件物品放入剩下容量为的背包中，再加上放第件物品的价值，此时能获得的最大价值就是。

优化空间复杂度

1
2
3

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= v; j--)
        f[j] = max(f[j], f[j - c[i]] + w[i]);

学习只用一维数组解01背包问题是十分必要的，尤其在完全背包问题中，后续会详细讲解。

初始化细节

有的题目要求”恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。这两种问法的区别是在初始化的时候有所不同。

①要求恰好装满背包：

为，其余为，分别对应恰好装满容量为的背包的最优解。

初始化的数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为的背包可能被价值为的 nothing “恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是了。

②没有要求必须把背包装满，而是只希望所装物品价值尽量大：

全部设为。

如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为，所以初始时状态的值也就全部为了。

模板题目

AC Wing 01背包

#include<iostream>
#include<algorithm>
#define MAXN 1005
int n , m ;  //n->物品 m->容量
int v[MAXN] ;//体积
int w[MAXN] ;//价值
int f[MAXN][MAXN] ;

using namespace std ;

int
main(int argc,char** argv)
{
    cin>>n>>m ;
    for(int i=1; i<=n; i++)
        cin>>v[i]>>w[i] ;
    for(int i=1; i<=n; i++){ // 前i个物品 
        for(int j=1; j<=m; j++){ // 对应物品的容量
            if(j<v[i]) f[i][j] = f[i-1][j] ;
            else{
                f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i]) ;
            }
        }
    }
    cout<< f[n][m] <<endl ;
    return 0 ;
}

洛谷干草出售

#include<iostream>
#include<algorithm>
#define MAXN 50005
int c,h ; // c->背包容量 h->稻草捆数
int v[MAXN] ; // 第 i 捆稻草的体积 vi
int f[MAXN] ;
using namespace std ;

int 
main(int argc,char** argv)
{
    cin>>c>>h ;
    for(int i=1; i<=h; i++) cin>>v[i] ;
    for(int i=1; i<=h; i++){
        for(int j=c; j>=v[i]; j--){
            f[j] = max(f[j],f[j-v[i]]+v[i]) ;
        }
    }
    cout<<f[c]<<endl;
    return 0 ;
}

洛谷疯狂地采药

#include<iostream>
#include<algorithm>
#define MAXN 50005
int c,h ; // c->背包容量 h->稻草捆数
int v[MAXN] ; // 第 i 捆稻草的体积 vi
int f[MAXN] ;
using namespace std ;

int 
main(int argc,char** argv)
{
    cin>>c>>h ;
    for(int i=1; i<=h; i++) cin>>v[i] ;
    for(int i=1; i<=h; i++){
        for(int j=c; j>=v[i]; j--){
            f[j] = max(f[j],f[j-v[i]]+v[i]) ;
        }
    }
    cout<<f[c]<<endl;
    return 0 ;
}

202209-2

何以包邮？

#include<iostream>
#define MAXN 600000
using namespace std ;

int n,x ;
int a[MAXN] ;
int f[MAXN];
main(int argc,char** argv)
{
    int sum = 0 ;
    cin>>n>>x ;
    for(int i=1;i<=n;i++){
        cin>>a[i] ;
        sum += a[i] ;
    } 
    int y = sum - x ; // 相当于价值
    for(int i=1; i<=n; i++){
        for(int j=y; j>=a[i]; j--){
            f[j] = max(f[j],f[j-a[i]]+a[i]);
        }
    }
    int ans = sum -f[y] ;
    cout<< ans <<endl;
    return 0 ;
}

Meta Field

CSP_2209