背包问题九讲源程序
1、01背包:
program ZeroOnePack;//01背包
const
maxv=20000;
maxn=3000;
var
f:array[0..maxv]of longint;
n,v:longint;
procedure main;
var
i,j,w,c,max:longint;
begin
readln(n,v);
for i:=0 to v do f:=0;
for i:=1 to n do
begin
readln(c,w);// 输入一个物品费用为c,价值为W
for j:=v downto 0 do
if c+j<=v then
if w+f[j]>f[c+j] then f[c+j]:=w+f[j];//状态转移方程
end;
max:=f[0];
for i:=1 to v do if f>max then max:=f;
writeln(max);
end;
begin
assign(input,'Pack.in');
reset(input);
assign(output,'Pack.out');
rewrite(output);
main;
close(input);
close(output);
end.
--------------------------------------------
2、完全背包
program CompletePack;//完全背包
const
maxv=20000;
maxn=3000;
var
f:array[0..maxv]of longint;
n,v:longint;
procedure main;
var
i,j,w,c,max:longint;
begin
readln(n,v);
for i:=0 to v do f:=0;
for i:=1 to n do
begin
readln(c,w);// 输入一个物品费用为c,价值为W
for j:=0 to v do//故意重复使用
if c+j<=v then
if w+f[j]>f[c+j] then f[c+j]:=w+f[j];//状态转移方程
end;
max:=f[0];
for i:=1 to v do if f>max then max:=f;
writeln(max);
end;
begin
assign(input,'Pack.in');
reset(input);
assign(output,'Pack.out');
rewrite(output);
main;
close(input);
close(output);
end.
------------
3、多重背包
program MultiplePack;//多重背包
const
maxv=20000;
maxn=3000;
var
f:array[0..maxv]of longint;
c,w,n:array[1..maxn]of longint;
num,v:longint;
procedure makeobject;
var
i,k,num2:longint;
begin
num2:=num;
for i:=1 to num do
begin
if c*n>v then n:=v div c;
k:=2;
while k*2-1<=n do//2进制思想
begin
inc(num2);
c[num2]:=c*k;w[num2]:=w*k;
k:=k*2;
end;
k:=n-k+1;
if k>0 then //补足n
begin
inc(num2);
c[num2]:=c*k;w[num2]:=w*k;
end;
end;
num:=num2;
end;
procedure main;
var
i,j,max:longint;
begin
readln(num,v);
for i:=1 to num do read(c,w,n);
makeobject;//制造倍数物品
for i:=0 to v do f:=0;
for i:=1 to num do
begin
for j:=v downto 0 do
if c+j<=v then
if w+f[j]>f[c+j] then f[c+j]:=w+f[j];//状态转移方程
end;
max:=f[0];
for i:=1 to v do if f>max then max:=f;
writeln(max);
end;
begin
assign(input,'Pack.in');
reset(input);
assign(output,'Pack.out');
rewrite(output);
main;
close(input);
close(output);
end.
............
4、混合背包
program BlendPack;//混合背包
const
maxv=20000;
maxn=3000;
var
f:array[0..maxv]of longint;
c,w,n,kind:array[1..maxn]of longint;
num,v:longint;
procedure makeobject;
var
i,k,num2:longint;
begin
num2:=num;
for i:=1 to num do
if kind=3 then
begin
kind:=1;
if c*n>v then n:=v div c;
k:=2;
while k*2-1<=n do//2进制思想
背包问题九讲和源程序(答案).txt 台湾一日不收复,我一日不过 4 级!如果太阳不出来了, 我就不去上班了;如果出来了,我就继续睡觉!目录 第一讲 01 背包问题...
背包问题九讲 v1 26页 免费 背包问题九讲源程序 3页 免费 背包问题九讲和... 如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击...
背包问题九讲和源程序(答案).txt我自横刀向天笑,笑完我就去睡觉。 你的手机比话费还便宜。路漫漫其修远兮,不如我们打的吧。目录第一讲 01背包问题这是最...
2背包问题九讲之完全背包问题_电脑基础知识_IT/计算机_专业资料。选填,简要... 背包问题九讲源程序 3页 免费 背包问题九讲 2.0 16页 免费 背包问题_九...
背包问题九讲_IT/计算机_专业资料。背包问题九讲 免费版老是看到网上有些把...例如不明白自己的程序为什么错了或者索要某种算 法的源代码, 使用这个联系方式...
1.6 小结 01背包问题是最基本的背包问题,它包含了背包问题中设计状态、方程的... 背包问题九讲源程序 3页 免费 动规-背包九讲完整版 26页 免费 背包问题_...
P05: 二维费用的背包问题问题二维费用的背包问题是指:对于每件物品,具有两种不... 背包问题九讲源程序 3页 免费 背包-问题九讲 17页 免费 背包九讲 2.0 ...
6背包问题九讲之分组的背包问题_电脑基础知识_IT/计算机_专业资料。选填,简要... 背包问题九讲源程序 3页 免费 背包-问题九讲 17页 免费 背包九讲 2.0 ...
背包问题九讲 v1.0 目录 第一讲 01 背包问题 第二讲 完全背包问题 第三讲...事实上,使用一维数组解 01 背包的程序在后面会被多次用到,所以这里抽象出 一个...
#include<stdio.h> #include<iostream.h> #define MAX 500//设置背包输入限... 背包问题九讲和源程序(答... 16页 免费 背包9讲 10页 免费 背包问题 14...
热门文档