限制背包
Program P1014;
const
maxv=120000;
n=6;
var
a:array[1..6] of longint;
i,j,k,l,v:longint;
f:array[0..maxv] of boolean;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
procedure CompletePack(cost:longint);
var
i:longint;
begin
for i:=cost to v do
f[i]:=f[i] or f[i-cost];
end;
procedure ZeroOnePack(cost:longint);
var
i:longint;
begin
if cost=0 then exit;
for i:=v downto cost do
begin
f[i]:=f[i] or f[i-cost];
end;
end;
procedure main;
var
i,j,k,l,sum,p:longint;
begin
v:=v div 2;
for i:=1 to n do
begin
if i*a[i]>=v then
begin
CompletePack(i);
continue;
end;
sum:=1;
k:=0;
while (a[i]-sum+1>0) do begin inc(k); sum:=sum*2; end;
dec(k);
sum:=1;
for j:=0 to k-1 do
begin
ZeroOnePack(sum*i);
sum:=sum*2;
end;
ZeroOnePack((a[i]-sum+1)*i);
if f[v] then
begin
writeln('Can be divided.');
exit;
end;
end;
if not(f[v]) then writeln('Can''t be divided.')
else writeln('Can be divided.')
end;
begin
for i:=1 to n do read(a[i]);
j:=1;
while (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]<>0) do
begin
writeln('Collection #',j,':');
fillchar(f,sizeof(f),false);
f[0]:=true;
v:=0;
for i:=1 to n do inc(v,i*a[i]);
if (v mod 2=1) then writeln('Can''t be divided.')
else
begin
main;
end;
writeln;
for i:=1 to n do read(a[i]);
inc(j);
end;
end.
分享到:
相关推荐
北大POJ1014-Dividing【DFS】【多重背包+二进制优化】 解题报告+AC代码
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
带上下界限制的背包问题(012背包) 3.线性的动态规划问题 积木游戏问题 决斗(判定性问题) 圆的最大多边形问题 统计单词个数问题 棋盘分割 日程安排问题 最小逼近问题(求出两数之比最接近某数/两数之和等于...
动态规划 01背包问题 POJ3624可以AC
经典的0-1背包问题. 适合新手学习. 原题网址:http://poj.grids.cn/problem?id=2773
晒代码之二——多重背包(POJ1276)
01背包问题 acm动态规划总结 PKU——DP专辑 背包之01 POJ 动态规划总结 背包之01背包、完全背包、多重背包详解 Dynamic+Programming 典型的动态规划,用递归下的记忆化搜索来实现 1088 POJ 动态规划加速原理之四边形...
背包问题 动态规划 POJ 3267 POJ 1260 POJ 1015 POJ 3176 POJ 1080 POJ 1159 POJ 2533 POJ 1836 Leetcode 70 Leetcode 309 搜索 DFS POJ 2488 POJ 3083 POJ 3009 POJ 1321 BFS POJ 3278 POJ 1426 POJ 3126 POJ 3414 ...
leetcode中国 MyAlgorithmSolutions ...背包问题 区间DP 区间问题 绝对值不等式 DP课 寒假每日一题 基础班 提高班 POJ 大二 2019 新生赛 蓝桥杯模拟 蓝桥杯学习 bfs 大数 dfs/抽象dfs 逻辑 测试 栈/递归 清华oj入门
#POJ 题集 数论 欧几里得/拓展欧几里得算法 1006 1061 搜索 普通搜索 1062, 1088, 2386 剪枝优化 1011 动态规划 背包 1014 高精度 加减乘除 1001 巧妙处理 思维处理 1852 模拟 1017 简单题 水题 1004 1007 1008 枚举...
2.10.1 一类开关问题,对 2 取模的 01 方程组 . . . . . . . . . . . . . . . . . . . 37 2.10.2 解同余方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.11 整数拆分 . . . . . . ....