A. 完全背包问题（c语言，pascal）
4.1 原始递归法
先看完全背包问题
一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，...,Wn,
每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多.
求旅行者能获得的最大总价值。
本问题的数学模型如下：
设 f(x)表示重量不超过x公斤的最大价值，
则 f(x）=max{f(x-i)+c[i]} 当x>=w[i] 1<=i<=n
可使用递归法解决问题程序如下:
program knapsack04;
const maxm=200;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
function f(x:integer):integer;
var i,t,m:integer;
begin
if x=0 then f:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(x-i)+c[i];
if m>t then t:=m;
end;
f:=t;
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
writeln(f(m));
end.
说明:当m不大时,编程很简单,但当m较大时,容易超时.
4.2 改进的递归法
改进的的递归法的思想还是以空间换时间,这只要将递归函数计算过程中的各个子函数的值保存起来,开辟一个
一维数组即可
程序如下:
program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
p:array[0..maxm] of integer;
function f(x:integer):integer;
var i,t,m:integer;
begin
if p[x]<>-1 then f:=p[x]
else
begin
if x=0 then p[x]:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(i-w[i])+c[i];
if m>t then t:=m;
end;
p[x]:=t;
end;
f:=p[x];
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
fillchar(p,sizeof(p),-1);
writeln(f(m));
end.
B. 哪位大神能帮我写一个“完全背包”问题的代码么谢谢！！ 最好用c或者c++ 写，有测试数据更～～～
完全背包问题，f[v] = max{f[v], f[v - w[i]] + v[i]}; 状态方程，用动态规划做网络下会有的
http://ke..com/view/841810.htm
C. 求完全背包问题的代码(C语言或C++版)或算法
背包问题小结- []2006-07-28
做到背包问题觉得很有意思，写写看看。
完全背包问题可以用贪心算法。
代码如下：
program bag1;
const maxn=10;
var
goods:array[1..maxn,1..3] of integer;
s:array[1..maxn] of real;
i,j:integer;
m,n:integer;
y:integer;
x:real;
function max:integer;
var m:real;
i,j:integer;
begin
m:=0;
for i:=1 to n do
if (goods[i,3]=0) and (m max:=j;
end;
procere choose;
var i,j:integer;
begin
while y begin
if y begin
i:=max;
if m>=y+goods[i,1] then begin goods[i,3]:=1;x:=x+goods[i,2];y:=y+goods[i,1];end else
begin
x:=x+(m-y)*s[i];
y:=m;
end;
end;
end;
end;
begin
fillchar(goods,sizeof(goods),0);
assign(input,'b.txt');
reset(input);
readln(m,n);
for j:=1 to n do
read(goods[j,1]);
readln;
for j:=1 to n do
read(goods[j,2]);
for j:=1 to n do
s[j]:=goods[j,2]/goods[j,1];
close(input);
choose;
writeln(x:5:2);
end.
编得不是很好 ^-^ 献丑了。
我来说说0/1背包问题。
状态：当前物品n
算符：j=0（当前物品不放入背包） 或 j=1（当前物品放入背包）
这就很好说了，还是把yes函数一改，问题OK了。
代码如下：
program bag2;
const maxn=10;
var i:integer;
goods:array[1..maxn,1..3] of integer;{原始数据}
s:array[1..maxn] of integer;{当前的状态}
r:array[1..maxn] of integer;{当前的总质量}
m:integer;{背包容量}
max:integer;{物品个数}
procere try(n:integer);
var j:integer;
{function yes:boolean;
var k:integer;
t:integer;
mn:integer;
begin
mn:=0;
t:=goods[n,3];
goods[n,3]:=j;
for k:=1 to n do
if goods[k,3]=1 then inc(mn,goods[k,1]);
goods[n,3]:=t;
if mn>m then yes:=false else yes:=true;
end;}
begin
if n=max+1 then begin if x for i:=1 to max do s[i]:=goods[i,3]; {保存最优解}end
end else
begin
if r[n-1]>m then exit;{已超过背包总容量}
for j:=1 downto 0 do
begin
if j=1 then r[n]:=r[n-1]+goods[n,1];
if j=0 then r[n]:=r[n]-goods[n,1];
if {yes}r[n]<=m then begin goods[n,3]:=j;try(n+1);goods[n,3]:=0;end
end;
end;
end;
begin
assign(input,'b.txt');
reset(input);
readln(m,max);
for i:=1 to max do
read(goods[i,1]);
readln;
for i:=1 to max do
read(goods[i,2]);
close(input);
try(1);
for i:=1 to 7 do
write(s[i]:3);
writeln;
writeln(x);
end.
用yes 函数要从头到当前求已装入背包物品的总质量，时间效率不高。所以我们引入r[n]数组来记录当前背包总质量（很好用！）注意用r[n-1]>m来做剪枝，以再次提高时间效率。
DC跟我说可以用二进制解此类问题。我觉得很有创意，也说说。比如8个物品，每个物品有0/1两种状态所以我们从(00000000)(二进制 )到（11111111）（二进制）循环即可。然后在分离十进制数对应起来即可。但在实际的操作中发现效率比回溯还低，我想有两方面的原因：1、显而易见，不可能做剪枝。2、每一次结果都要从1到8求和十效率降低。不过这确实是一种很新颖的算法。
D. 背包问题C语言简短代码，大神们最好带解释和注释，谢谢！！！
不知道你说的哪种类型的背包，我就说下最简单的吧。
一、01背包
问题描述：有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
（1）基本思路：这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。
意思简要来说就是：如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
（2）优化空间复杂度：以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符。
（3）初始化的细节问题：我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。
如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。
为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。
【写的伪代码，能看懂哈。。。不懂再问好了】
E. 完全背包问题O(VN)的算法C++源码
#include<iostream>
usingnamespacestd;
#defineMAXN=501;
intf[MAXN];
intmain(){
intn,x,y,v;
cin>>n>>v;
for(inti=0;i<n;i++){
cin>>x>>y;
for(intj=x;j<=v;j++)
if(f[j]<f[j-x]+y)f[j]=f[j-x]+y;
}
cout<<f[v]<<endl;
return0;
}
其中n为物品种数，v为背包容量，x为物品体积，y为价值
F. 求动态规划01背包问题c语言的代码，要稍微简单且无错的。谢谢
我写个C++的。
#include<iostream>
#define MAX 1111
using namespace std;
int f[MAX],n,m,v,w;
int main(){
cin>>n>>m;//n表示个数，m表示背包容量
for(int i=1;i<=n;++i){
cin>>v>>w;//v=价值，w=重量
for(int j=m;j>=w;--j)
if(f[j]<f[j-w]+v)
f[j]=f[j-w]+v;
}
cout<<f[m]<<'\n';
return 0;
}
C++和C应该都差不多吧。。这个最简洁了 。顺便一句，如果要能无限放的话
for(int j=m;j>=w;--j)这一句变成for(int j=w;j<=m;++j)就行了。
G. 求用A*算法解01背包问题的C语言编的完整的源代码，在线等，高人们帮帮我，谢谢~
这个算法厉害。
#include "stdafx.h"
#include <iostream>
using namespace std;
#define N 7//物品数量
#define S 20//要求背包重量
int W[N+1]=;//各物品重量，W[0]不使用。。。
int knap(int s,int n)//s为剩余重量，n为剩余可先物品数。。
{
if(s==0)return 1;//return 1 means success..
if(s<0||(s>0&&n<1))return 0;//如果s<0或n<1则不能完成
if(knap(s-W[n],n-1))//从后往前装，如果装满第n个包，剩余的重量仍然可以在剩余的n-1包中放下，那么就将第n个包装满。
{
printf("%4d",W[n]);//打印第n个包的容量，即装进第n个包的重量。
return 1;
}
return knap(s,n-1);//如果装满第n个包后，剩余的重量不能在剩余的n-1包中放下，那么就不用第n个包，考虑能不能用第n-1个包。
}
void main()
{
if(knap(S,N))printf("\nOK!\n");
else printf("Failed!");
}
H. 求大神给一份C语言01背包的代码，要每一行都有注释，谢谢！
这是一个背包问题，该算法已经是最简单的了，还有递归算法，我觉得更麻烦。对你的代码进行解释如下：
//背包问题：有m件物品和一个承重为t的背包。第i件物品的重量是w[i]，价值是v[i]。
//求解将哪些物品装入背包可使这些物品的重量总和不超过背包承重量t，且价值总和最大。
#include<stdio.h>
#include<conio.h>
#include<string.h>
intf[1010],w[1010],v[1010];//f记录不同承重量背包的总价值，w记录不同物品的重量，v记录不同物品的价值
intmax(intx,inty){//返回x,y的最大值
if(x>y)returnx;
returny;
}
intmain(){
intt,m,i,j;
memset(f,0,sizeof(f));//总价值初始化为0
scanf("%d%d",&t,&m);//输入背包承重量t、物品的数目m
for(i=1;i<=m;i++)
scanf("%d%d",&w[i],&v[i]);//输入m组物品的重量w[i]和价值v[i]
for(i=1;i<=m;i++){//尝试放置每一个物品
for(j=t;j>=w[i];j--){
f[j]=max(f[j-w[i]]+v[i],f[j]);
//在放入第i个物品前后，检验不同j承重量背包的总价值，如果放入第i个物品后比放入前的价值提高了，则修改j承重量背包的价值，否则不变
}
}
printf("%d",f[t]);//输出承重量为t的背包的总价值
printf(" ");
getch();
return0;
}
I. 完全背包问题，c语言编程
#include<stdio.h>
float V[1000],V1[1000];
int max(float a[],int n)
{
int s = 1;
float fmax = a[1];
for (int j=2;j<n;j++)
{
if (a[j]>fmax)
{
fmax = a[j];
a[j] = 0;
s = j;
}
}
return s;
}
int KnapSack(int n,int w[],int v[],int C)
{
int Maxvalue = 0;
int X[1000],w0[1000],w1[1000];
memset(X,0,sizeof(X));
memset(w0,0,sizeof(w0));
memset(w1,0,sizeof(w0));
for (int j=1;j<n;j++)
{
V[i] = 1.0*v[i]/w[i];
V1[i] =V[i];
}
X[1] = max(V1,n);
int w0[1] = n/w[X];
int w1[1] = n%w[X];
int k = 1;
while (w1[k++]!=0)
{
X[K] = max(V1,n);
w0[k] = w1[k]/w[Y];
w1[k] = w1[k]%w[Y];
}
for (int m=1;m<k;m++)
{
Maxvalue+=w0[m]*w[X[K]]*v[X[k];
}
return Maxvalue;
}
int main(void)
{
int s;
int w[1000];
int v[1000];
int n,i;
int C;
scanf("%d %d", &C, &n);
for(i=0;i<n;i++)
scanf("%d %d",&w[i], &v[i]);
s=KnapSack(n,w,v,C);
printf("%d",s);
return 0;
}
J. 完全背包问题，用C语言编译的代码~是所有代码，不是一段关键代码。
参考代码：
/*
* n：物品种类 每种只能选取一种
* capacity：背包容量
* c[i]：第i种物品的花费 cost
* v[i]：第i种物品的价值 value
* f[j]：i状态下容量为j时背包可获得的最大价值
*/
int getMaxValue(int n,int capacity){
for(int i=0;i<n;i++)
for(int j=capacity;j>=0;j--)
if(i==0){
if(j>=c[i])f[j]=v[i];
else f[j]=0;
}
else if(j>=c[i])f[j]=max(f[j],f[j-c[i]]+v[i]);
return f[capacity];
}