c语言背包问题背包问题的C语言描述

编程实现0－1背包问题的求解

可惜我是学PASCAL的pascal的代码是：

var m,n,j,i:integer; c,w:array[1..200] of integer; f:array[0..200,0..30] of integer; function q(x,y:integer):integer; begin if x>y then q:=x else q:=y; end; begin readln(m,n); for i:= 1 to n do readln(w[i],c[i]); for i:=1 to m do f[0,i]:=0; for i:=1 to n do f[i,0]:=0; for i:=1 to n do for j:=1 to m do begin if j>=w[i] then f[i,j]:=q(f[i-1,j-w[i]]+c[i],f[i-1,j]) else f[i,j]:=f[i-1,j]; end; writeln(f[n,m]); end.

不会C++

你加油吧

思路是：设f(i,x)表示前i件物品，总重量不超过x的最优价值，则f(i,x)=max(f(i-1,x-w[i])+c[i],f(i-1,x)){第i件物品放进去与不放进去的更优方案}，f(n,m)即为最优解。

C语言，算法，动态规划。对于0-1背包问题，我有个小疑问。

dp(i,j)表示前i件物品选择任意件后放进最大容量为j的背包的最大价值。

显然，dp(0,j)=0，dp(i,0)=0。

对于第i件物品，有两种情况： 一、不放进背包，则最大价值为前i-1件物品可以放进容量为j的背包的最大价值，即dp(i,j)=dp(i-1,j) 二、放进背包，则最大价值为第i件物品价值加上前i-1件物品卡伊放进容量为j-w[i]的背包的最大价值，即dp(i,j)=v[i]+dp(i-1,j-w[i) 综合两种情况 dp(i,j)=max{dp(i-1,j), v[i]+dp(i-1,j-w[i)}

背包问题的C语言描述

#include <stdio.h> #define N 7//物品数量 #define S 15//要求背包重量 int W[N+1]={0,1,4,3,4,5,2,7};//各物品重量，W[0]不使用。

。

。

int knap(int s,int n)//s为剩余重量，n为剩余可先物品数。

。

{ if(s==0)return 1;//return 1 means ess.. if(s<0||(s>0&&n<1))return 0; if(knap(s-W[n],n-1)) { printf("%4d",W[n]); return 1; } return knap(s,n-1); } void main() { if(knap(S,N))printf(" OK! "); else printf("Failed!"); } #include <stdio.h> #define N 7 #define S 15 typedef struct { int S； int n： int job； } KNAPTP； int w[N+1] = {0，1，4，3，4，5，2，7}； int knap(int S，int n)； main(){ if ( knap(S，N) ) printf("0K! " )； else printf( "N0! " )； int knap( int S，int n ) { KNAPTP stack[100]，x； ， k， rep； x.s = s； x.n = n； x.job = 0； = l； ] = x； k = 0； while (>0&&!k ) { x = ]； rep = l； while ( !k && rep ) { if( x.s＝0 ) k = 1； /*已求得一组解*/ else if ( x.S<0 || x.n<=0 ) rep = 0； else { x.s = x.s-w[x.n--] ； x.job=1； stack[+] = x； } } if ( !k ) { rep = 1； while ( >= 1 && rep) { x = --]； if ( x.job＝1){ x.s += w[x.n + 1]； x.job = 2； stack[+] = x； rep=0 ； } } } } if (k){ */输出一组解*/ while ( >= 1 ) { x = StaCk [-- ]； if ( x.job == 1 ) printf ( "M ，w[x.n+1] )； } } return k； }