首页 > 代码库 > uva--624Word Amalgamation+dp
uva--624Word Amalgamation+dp
其实就是0 1背包问题,不过还要输出路径。对于路径输出,我们可以记录在装容量为v的背包时,物品i有没有使用。然后最后从最大容量和最大物品编号往回推即可。
代码如下:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int dp[10010],g[50][10100]; int main() { int V; while(scanf("%d",&V)!=EOF) { int n,a[50]; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); memset(dp,0,sizeof(dp)); memset(g,0,sizeof(g)); for(int i=n;i>=1;i--) for(int j=V;j>=a[i];j--) { if(dp[j]<dp[j-a[i]]+a[i]) { dp[j]=dp[j-a[i]]+a[i]; g[i][j]=1; } } int i=1,v=V; while(i<=n) { if(g[i][v]==1) { printf("%d ",a[i]); v=v-a[i]; } i++; } printf("sum:%d\n",dp[V]); } return 0; }
uva--624Word Amalgamation+dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。