首页 > 代码库 > UVA 624 CD
UVA 624 CD
01背包。 不仅要求出最大的。还要求出最大的由那些构成。
多定义一个path[]就可以了。
应该是 Special Judge
我样例最后一组输出的是 43 2 sum:45
样例输出的是 4 10 12 9 8 2 sum:45
不过也AC了。
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<vector> #include<cmath> #define INF 0x7fffffff #define eps 1e-8 #define LL long long #define PI 3.141592654 #define CLR(a,b) memset(a,b,sizeof(a)) #define FOR(i,a,b) for(int i=a;i<b;i++) #define FOR_(i,a,b) for(int i=a;i>=b;i--) #define pb push_back #define mp make_pair #define ft first #define sd second #define sf scanf #define pf printf #define sz(v) ((int)(v).size()) #define all(v) (v).begin(),(v).end() #define acfun std::ios::sync_with_stdio(false) #define SIZE 100000 +1 using namespace std; int n,m; int path[SIZE]; int a[21]; int dp[SIZE]; void zeroonepack(int cost,int value) { FOR_(i,m,cost) { //dp[i]=max(dp[i],dp[i-cost]+value); if(dp[i-cost]+value>dp[i]) { dp[i]=dp[i-cost]+value; path[i]=i-cost; } } } int main() { while(~sf("%d%d",&m,&n)) { FOR(i,0,n) sf("%d",&a[i]); CLR(dp,0); CLR(path,-1); FOR(i,0,n) zeroonepack(a[i],a[i]); int ans=0,k=-1; FOR(i,0,m+1) { if(dp[i]>ans) ans=dp[i],k=i; } stack<int>out; while(path[k]!=-1) { //pf("%d ",k-path[k]); out.push(k-path[k]); k=path[k]; } while(!out.empty()) { pf("%d ",out.top()); out.pop(); } pf("sum:%d\n",ans); } }
UVA 624 CD
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。