数字组合

题意

给定 N个正整数，从中选出若干个数，使它们的和为 M，求有多少种选择方案。

思考

01背包：n个物品，重量ai，背包容量为m，储存方案数。

#include<bits/stdc++.h>

using namespace std;

int a[110],f[10010],n,m;

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    f[0]=1;
    
    for(int i=1;i<=n;i++){
        for(int j=m;j>=a[i];j--){
            f[j]+=f[j-a[i]];
        }
    }
    cout<<f[m];
}

自然数拆分

题意

给定一个自然数 N，要求把 N 拆分成若干个正整数相加的形式，参与加法运算的数可以重复。

注意:

拆分方案不考虑顺序；
至少拆分成 2 个数的和。

求拆分的方案数 mod2147483648 的结果。

思考

每个数看成一个物品，完全背包。记得开long long

#include<bits/stdc++.h>
using namespace std;
const int N=4010,mod = 2147483648;
long long n,f[N];
int main(){
    cin>>n;
    
    f[0]=1;
    for(int i=1;i<n;i++){
        for(int j=i;j<=n;j++){
           f[j]=(f[j]+f[j-i])%mod; 
        }
    }
    cout<<f[n]<<endl;
    return 0;
}

陪审团

题意

从n物品中选m个，每个物品有两个参数：p,d。使得m个物品p的总和和d的总和差的绝对值最小的，如果有多总方案，选择p+d的和最大的一组。此外还要求输出选择的是哪些物品。

1≤N≤200
1≤M≤20
0≤p[i],d[i]≤20

思考

差从-400~400，共800总情况。总价值0-800

状态表示：f[i][j][k]：从前i个人中选j个，差值是k的所有方案的集合。储存p+d最大的

状态转移：考虑选和不选第i个人

不选：f[i-1][j][k]

选：不变的部分+变的部分：f[i-1][j-1][k-(pi-di)]+pi+di。记得判断不合法的情况

如何求具体方案:
从终点开始逆向判断，看每一种状态是从哪一种状态转移过来的。

#include<bits/stdc++.h>

using namespace std;
const int N=210,M=810,bios=400;
int f[N][22][M];  //因为要记录具体方案，不能用滚动数组
int p[N],d[N];
int ans[N],cnt,n,m;

int main(){
    int T=1;
    while(scanf("%d%d",&n,&m),n||m){
        cnt=0;
        for(int i=1;i<=n;i++) scanf("%d%d",&p[i],&d[i]);
        memset(f,-0x3f,sizeof(f));
        f[0][0][bios]=0;
        
         for (int i = 1; i <= n; i ++ )
            for (int j = 0; j <= m; j ++ )
                for (int k = 0; k < M; k ++ )
                {
                    f[i][j][k] = f[i - 1][j][k];
                    int t = k - (p[i] - d[i]);
                    if (t < 0 || t >= M) continue;
                    if (j < 1) continue;
                    f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][t] + p[i] + d[i]);
                }
        
        int v=0;
        while(f[n][m][v+bios]<0&&f[n][m][bios-v]<0) v++;
        
        if(f[n][m][-v+bios]>f[n][m][v+bios]) v=bios-v;
        else v=bios+v;
        
        int x=n,y=m,k=v;
        while(y){
            if(f[x][y][k] == f[x-1][y][k]) x--;
            else{
                ans[cnt++]=x;
                k-=(p[x]-d[x]);
                x--,y--;
            }
        }
        
        int sp=0,sd=0;
        for(int i=0;i<cnt;i++) sp+=p[ans[i]],sd+=d[ans[i]];
        
        printf("Jury #%d\n", T ++ );
        printf("Best jury has value %d for prosecution and value %d for defence:\n", sp, sd);

        sort(ans, ans + cnt);
        for (int i = 0; i < cnt; i ++ ) printf(" %d", ans[i]);
        printf("\n\n");
    }
    
}