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

c语言背包问题  时间:2021-07-03  阅读:()

编程实现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; }

随风云25元/月 ,德阳高防云服务器 2核2G 10M 75元/月 内蒙古三线BGP服务器 2核2G 5M

公司介绍成都随风云科技有限公司成立于2021年,是国内领先的互联网业务平台服务提供商。公司专注为用户提供低价高性能云计算产品,致力于云计算应用的易用性开发,并引导云计算在国内普及。目前公司研发以及运营云服务基础设施服务平台(IaaS),面向全球客户提供基于云计算的IT解决方案与客户服务,拥有丰富的国内BGP、双线高防、香港等优质的IDC资源。公司一直秉承”以人为本、客户为尊、永续创新&...

星梦云:四川100G高防4H4G10M月付仅60元

星梦云怎么样?星梦云资质齐全,IDC/ISP均有,从星梦云这边租的服务器均可以备案,属于一手资源,高防机柜、大带宽、高防IP业务,一手整C IP段,四川电信,星梦云专注四川高防服务器,成都服务器,雅安服务器。星梦云目前夏日云服务器促销,四川100G高防4H4G10M月付仅60元;西南高防月付特价活动,续费同价,买到就是赚到!点击进入:星梦云官方网站地址1、成都电信年中活动机(成都电信优化线路,封锁...

spinservers($89/月),圣何塞10Gbps带宽服务器,达拉斯10Gbps服务器

spinservers是Majestic Hosting Solutions LLC旗下站点,主要提供国外服务器租用和Hybrid Dedicated等产品的商家,数据中心包括美国达拉斯和圣何塞机房,机器一般10Gbps端口带宽,高配置硬件,支持使用PayPal、信用卡、支付宝或者微信等付款方式。目前,商家针对部分服务器提供优惠码,优惠后达拉斯机房服务器最低每月89美元起,圣何塞机房服务器最低每月...

c语言背包问题为你推荐
bloomfilter如何用Java写一个爬虫jqlDX5JQL8WDPMW求大神帮查下是不是行货苹果调度系统1.说明高级调度、中级调度和低级调度的基本含义。editplus破解版cool edit pro 2.1汉化破解版清除电脑垃圾怎么删除电脑垃圾?mediasres什么意思数据分析报告范文数据分析报告怎么写图片存储怎么把存图片存储另一种方式?12306注册铁路12306怎么注册用户名丁香园网站丁香园主网站用的是什么程序??谁能看的出来??
krypt lamp photonvps 香港机房 私服服务器 2017年黑色星期五 lamp配置 浙江独立 777te bgp双线 网站木马检测工具 上海服务器 卡巴斯基免费试用版 华为云服务登录 raid10 免费稳定空间 广州服务器托管 windowsserver2008 美国vpn代理 linux服务器系统 更多