PAT甲题题解-1068. Find More Coins (30)-dp,01背包

一开始没多想，虽然注意到数据N<=10^4的范围，想PAT的应该不会超时吧，就理所当然地用dfs做了，结果最后一组真的超时了。
剪枝啥的还是过不了，就意识到肯定不是用dfs做了。
直到看到别人说用01背包的思路，果真好久没做题了智力水平下降，且原本dp就是我的弱项，压根就没把这题往dp上去想额。。。

(http://www.liuchuo.net/archives/2323)

题意：从n个硬皮中选取方案，使得总和价值正好为m，如果有多种，方案为排列最小的那个。

可以把硬币看成w=v(即容量=价值)的物品，现在要选取这些物品放入到容量为m的背包中，求能装的最大价值。
如果最大价值恰好等于容量m，那么方案则是可行的，否则输出No Solution。
由于要输出排列最小的方案，所以先将硬币按价值从大到小排列，相当于我先装大的，再装小的。
接着用01背包的方法求dp[j]。
chosen[i][j]数组表示背包里容量为j的时候，是否含有第i个物品，用于最后序列的输出。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <string.h>

#include <vector>

#define INF 0x3f3f3f3f

using namespace std;

const int maxn=+;

const int maxv=;

int coins[maxn];

int dp[maxv]; //dp[v]表示：总和加起来=v的序列中最后一个值最小为多少。

int chosen[maxn][maxv];

int ans[maxn];

int cnt=;

bool cmp(int a,int b){

    return a>b;

}

int main()

{

    int n,m;

    scanf("%d %d",&n,&m);

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

        scanf("%d",&coins[i]);

    }

    sort(coins,coins+n,cmp);

    dp[]=;

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

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

                if(dp[j]<=dp[j-coins[i]]+coins[i]){

                    dp[j]=dp[j-coins[i]]+coins[i];

//printf("i:%d j:%d dp:%d chosen:%d\n",i,j,dp[j],coins[i]);

                    chosen[i][j]=;

                }

        }

    }

    if(dp[m]!=m){

        printf("No Solution");

    }

    else{

        int v=m,idx=n-;

        while(v){

            if(chosen[idx][v]){

                ans[cnt++]=coins[idx];

                v-=coins[idx];

            }

            idx--;

        }

        printf("%d",ans[]);

        for(int i=;i<cnt;i++)

            printf(" %d",ans[i]);

    }

    return ;

}

PS：想了解背包问题的，有个《背包九讲》，网上可以搜搜看看，挺好的

巴特西

PAT甲题题解-1068. Find More Coins (30)-dp,01背包

最新文章

热门文章