I - The Values You Can Make （背包求具体方案）

题目大意

给你n个数，让你用这n个数在组成k的情况下，找到所有的value，这些value也由这n个数组成，且这些value组合在一起能够组成k

解法

看到题目我的想法就是母函数= =不过wa了，后来发现因为母函数能找到这n个数所能形成的所有情况，但是可能两种情况是包含关系的。比如3,3,6这个数据可以形成6和9但是如果k是15的时候，你就不能得到因为9是由6生成的
dp[i][j]表示在和为i的情况下，能否得到j
那么当dp[i][j] = 1时，dp[i][j + c[k]]比然能得到，dp[i+c[k]][j+c[k]]也能得到。

C++代码

/**

6 18

5 6 1 10 12 2

dp[i-c[i]][k] -> dp[i][k],dp[i][k+c[i]]

*/

#include<bits/stdc++.h>

using namespace std;

int a[];

int res[];

int dp[][];

int main(){

    int n , m ;

    cin >> n >> m;

    for(int i = ; i <= n ; i++){

        cin >> a[i];

    }

    sort(a+,a++n);

    dp[][] = ;

    for(int i = ;i <= n ; i++){

        for(int j = m;j >= a[i];j --){

            for(int k = ;k + a[i]<= m;k ++){

                if(dp[j - a[i]][k]) dp[j][k] = dp[j][k+a[i]] = ;

            }

        }

    }

    int tot = ;

    for(int i = ;i <= m; i ++) if(dp[m][i]) res[tot++] = i;

    printf("%d\n",tot);

    for(int i = ;i < tot;i ++) printf("%d ",res[i]);

}

巴特西

I - The Values You Can Make （背包求具体方案）

题目大意

解法

C++代码

最新文章

热门文章