国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

UVA.562 Dividing coins (DP 01背包)

2019-11-08 19:45:43
字體：大 中 小
來源：轉載
供稿：網友

UVA.562 Dividing coins (DP)

題意分析

給出一堆不同面額的硬幣，要求將這這些硬幣分為價值接近的2堆（越接近越好，相等的情況最佳，且單個硬幣不可再分），并最后輸出這2堆硬幣價值差值的絕對值。

先累加求出這堆硬幣的總和sum，然后令sum/2為背包容量，所有硬幣為商品做01背包即可。最后求出的解為其中一堆最多能分多少價值的硬幣（設為x)，那么另一堆硬幣的價值為sum-x，故兩堆硬幣的差值為sum-x*2。

核心狀態轉移方程： dp[i][j] = max(dp[i][j],dp[i-1][j-a[i]]+a[i])

代碼總覽

/* Title:UVA.562 Author:pengwill Date:2017-2-16*/#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define nmax 105#define mc 50000using namespace std;int a[nmax],dp[nmax][mc];int main(){ int t; scanf("%d",&t); while(t--){ int n,c = 0; scanf("%d",&n); memset(dp,0,sizeof(dp)); memset(a,0,sizeof(a)); for(int i = 1; i<=n; ++i) {scanf("%d",&a[i]); c+=a[i];} for(int i =1; i<=n;++i){ for(int j = 0;j<=c/2;++j){ dp[i][j] = dp[i-1][j]; if(j>=a[i]) dp[i][j] = max(dp[i][j],dp[i-1][j-a[i]]+a[i]); } }

發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板： 嘉禾县| 镇平县| 辉县市| 龙游县| 湾仔区| 衡南县| 柘荣县| 文山县| 肃宁县| 兴宁市| 平江县| 华安县| 云霄县| 焉耆| 米脂县| 杭州市| 锡林郭勒盟| 南乐县| 鞍山市| 秭归县| 墨竹工卡县| 特克斯县| 德州市| 西乌| 遂溪县| 桐乡市| 梁平县| 柳州市| 义马市| 万载县| 观塘区| 桂平市| 隆安县| 德惠市| 丰原市| 彭州市| 凯里市| 尼勒克县| 安泽县| 祁门县| 罗定市|