红鲤鱼与绿鲤鱼与驴

今天把昨天学的背包问题的练习做了一下

1、题意：在N个数中找出其和为M的若干个数。先读入正整数N（1<N<100）和M(1<M<10000)， 再读入N个正数（可以有相同的数字，每个数字均在1000以内），在这N个数中找出若干个数， 使它们的和是M，把满足条件的数字组合都找出来以统计组合的个数，输出组合的个数（不考虑组合是否相同）。

2、思路：典型的01背包问题，n个整数看作n个物品，m看作背包容量，在外层循环到i时，设f[j]表示“和为j”时有多少种方案。把原来的max改成求和就行了

3、普通代码：

#include<iostream>
using namespace std;
int a[105];
int f[105][10005];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    f[0][0]=1;
    for (int i = 1; i <= n; i++){
        for (int j = m; j >= 0; j--)
            f[i][j] += f[i - 1][j];
        for (int j = m; j >= a[i]; j--)
            f[i][j] += f[i - 1][j - a[i]];
    }
    cout<<f[n][m]<<endl;
    return 0;
}

4、进阶代码：（昨天学的优化）

#include<iostream>
using namespace std;
int a[105];
int f[10005];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>a[i];
    f[0]=1;
    for(int i=0;i<n;i++)
        for(int j=m;j>=a[i];j--)
            f[j]+=f[j-a[i]];
    cout<<f[m]<<endl;
    return 0;
}

1、题意：给定一个自然数N，要求把N拆分成若干个正整数相加的形式，参与加法运算的数可以重复。求拆分的方案数 mod 2147483648 拆分的方案数 mod 2147483648 拆分的方案数mod2147483648的结果。1≤N≤4000

2、思路：经典的完全背包问题，物品就是自然数 1 ~ n-1，背包容量是n，把原来的max改成求和就行了，记得 mod 2147483648

3、代码：

#include<iostream>
using namespace std;
int f[4005];
int main()
{
    int n; 
    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])%2147483648u;
    cout<<f[n];
    return 0;
}

前两道难道还可以 最后一道压轴题啃了半天

书和视频看了好几遍 有点郁闷
题意和思路就不写了 直接上代码
跟着yxc大佬的视频 打了代码和注释
这两天还要再多看两遍 争取完全理解

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;
const int N=205;
const int M=805; //从-400到400 一共801中情况 
const int base=400; //将得分的差看作"体积" 可能是负数 所以加一个偏差值 

int p[N],d[N];
int f[N][25][M];
int ans[N];

int main()
{
    int T = 1;
    int n,m;
    while (scanf("%d%d", &n, &m), n || m) 
    {
        for (int i = 1; i <= n; i ++ ) 
            scanf("%d%d", &p[i], &d[i]);

        memset(f, -0x3f, sizeof f);
        f[0][0][base] = 0; //base表示差值为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]; //不选择i的状态 
                    int t = k - (p[i] - d[i]); //计算差值 判断选择i的状态 是否成立 
                    if (t < 0 || t >= M) continue; //判断差值是否在范围内 
                    if (j < 1) continue; //选择i了所以j>1 
                    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][base - v] < 0 && f[n][m][base + v] < 0) 
            v ++ ; //找出最小的差值 

        if (f[n][m][base - v] > f[n][m][base + v]) //判断正负哪种和更大 
            v = base - v;
        else 
            v = base + v;

        int cnt = 0;
        int i = n, j = m, k = v;
        while (j) //还没有找够人 
        {
            if (f[i][j][k] == f[i - 1][j][k]) //相等则可以不选 
                i -- ; 
            else //选择即更新状态 
            {
                ans[cnt ++ ] = i;
                k -= (p[i] - d[i]);
                i --;
                j --;
            }
        }

        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]);
       puts("\n"); //两个回车
    }
    return 0;
}

自言自语Part：
本来计划上午做四道题 下午继续学新东西 结果下午又忙屁孩小升初和新闻稿的事了
可能这就是传说中计划赶不上变化吧 不过晚上回来还是坚持把最后一道题做了
并且坚定的拒绝了强哥抛来的打游戏的橄榄枝 哎 他们又要说我放他们鸽子了
其实后面还有一道抛硬币的题 不过一看到难度是困难 果断撤退 以后有机会了把它在补上吧
Good Luck！ 今天只能算0.5咯