请选择 进入手机版 | 继续访问电脑版

[XDOJ-174]分配宝藏(dp集合,未完待续)

[复制链接]
冰宇 发表于 2020-12-31 18:57:12 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
动态规划



动态规划解题思路:

1.大事化小
2.确定状态
3.界限条件(小事化了)
4.状态转移方程
01背包问题

[XDOJ-174]分配宝藏(垂纶用)

  两个寻宝者找到一个宝藏,内里包含n件物品,
每件物品的价值分别是W[0],W[1],…W[n-1]。
SumA代表寻宝者A所获物品价值总和,
SumB代表寻宝者B所获物品价值总和,
请问怎么分配才气使得两人所获物品价值总和差距最小,
即两人所获物品价值总和之差的绝对值|SumA - SumB|最小。
<blockquote>  
输入说明
输入数据由两行构成:
第一行为一个正整数n,体现物品个数,此中0=w)                        dp[j]=max(dp[j],dp[j-w]+w);                        if(dp[j]>ans)ans=dp[j];                }        }//        cout>v;        }        for(int j=0;j=w[1])        dp[1][j]=v[1];                else dp[1][j]=0;        }        for(int i=2;ians)ans=dp[j];//时刻更新ans最大值                }        }        coutN;        cout
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )