06普及组开心的金明程序思路 在pascal语言中，如何在一个数组中选取5个数，使其之和最...
pascal \u8c01\u53ef\u4ee5\u8bb2\u89e3\u4e00\u4e0b\u8fd9\u4e2a\u5f00\u5fc3\u7684\u91d1\u660e\u8fd9\u4e2a\u7b80\u77ed\u7684\u7a0b\u5e8f\uff08\u7cbe\u8bb2\uff09\u9898\u76ee\u6709N\u4ef6\u7269\u54c1\u548c\u4e00\u4e2a\u5bb9\u91cf\u4e3aV\u7684\u80cc\u5305\u3002\u7b2ci\u4ef6\u7269\u54c1\u7684\u8d39\u7528\u662fc[i]\uff0c\u4ef7\u503c\u662fw[i]\u3002\u6c42\u89e3\u5c06\u54ea\u4e9b\u7269\u54c1\u88c5\u5165\u80cc\u5305\u53ef\u4f7f\u4ef7\u503c\u603b\u548c\u6700\u5927\u3002\u57fa\u672c\u601d\u8def\u8fd9\u662f\u6700\u57fa\u7840\u7684\u80cc\u5305\u95ee\u9898\uff0c\u7279\u70b9\u662f\uff1a\u6bcf\u79cd\u7269\u54c1\u4ec5\u6709\u4e00\u4ef6\uff0c\u53ef\u4ee5\u9009\u62e9\u653e\u6216\u4e0d\u653e\u3002\u7528\u5b50\u95ee\u9898\u5b9a\u4e49\u72b6\u6001\uff1a\u5373f[i][v]\u8868\u793a\u524di\u4ef6\u7269\u54c1\u6070\u653e\u5165\u4e00\u4e2a\u5bb9\u91cf\u4e3av\u7684\u80cc\u5305\u53ef\u4ee5\u83b7\u5f97\u7684\u6700\u5927\u4ef7\u503c\u3002\u5219\u5176\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\u4fbf\u662f\uff1af[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}\u8fd9\u4e2a\u65b9\u7a0b\u975e\u5e38\u91cd\u8981\uff0c\u57fa\u672c\u4e0a\u6240\u6709\u8ddf\u80cc\u5305\u76f8\u5173\u7684\u95ee\u9898\u7684\u65b9\u7a0b\u90fd\u662f\u7531\u5b83\u884d\u751f\u51fa\u6765\u7684\u3002\u6240\u4ee5\u6709\u5fc5\u8981\u5c06\u5b83\u8be6\u7ec6\u89e3\u91ca\u4e00\u4e0b\uff1a\u201c\u5c06\u524di\u4ef6\u7269\u54c1\u653e\u5165\u5bb9\u91cf\u4e3av\u7684\u80cc\u5305\u4e2d\u201d\u8fd9\u4e2a\u5b50\u95ee\u9898\uff0c\u82e5\u53ea\u8003\u8651\u7b2ci\u4ef6\u7269\u54c1\u7684\u7b56\u7565\uff08\u653e\u6216\u4e0d\u653e\uff09\uff0c\u90a3\u4e48\u5c31\u53ef\u4ee5\u8f6c\u5316\u4e3a\u4e00\u4e2a\u53ea\u7275\u626f\u524di-1\u4ef6\u7269\u54c1\u7684\u95ee\u9898\u3002\u5982\u679c\u4e0d\u653e\u7b2ci\u4ef6\u7269\u54c1\uff0c\u90a3\u4e48\u95ee\u9898\u5c31\u8f6c\u5316\u4e3a\u201c\u524di-1\u4ef6\u7269\u54c1\u653e\u5165\u5bb9\u91cf\u4e3av\u7684\u80cc\u5305\u4e2d\u201d\uff0c\u4ef7\u503c\u4e3af[i-1][v]\uff1b\u5982\u679c\u653e\u7b2ci\u4ef6\u7269\u54c1\uff0c\u90a3\u4e48\u95ee\u9898\u5c31\u8f6c\u5316\u4e3a\u201c\u524di-1\u4ef6\u7269\u54c1\u653e\u5165\u5269\u4e0b\u7684\u5bb9\u91cf\u4e3av-c[i]\u7684\u80cc\u5305\u4e2d\u201d\uff0c\u6b64\u65f6\u80fd\u83b7\u5f97\u7684\u6700\u5927\u4ef7\u503c\u5c31\u662ff[i-1][v-c[i]]\u518d\u52a0\u4e0a\u901a\u8fc7\u653e\u5165\u7b2ci\u4ef6\u7269\u54c1\u83b7\u5f97\u7684\u4ef7\u503cw[i]\u3002\u4f18\u5316\u7a7a\u95f4\u590d\u6742\u5ea6\u4ee5\u4e0a\u65b9\u6cd5\u7684\u65f6\u95f4\u548c\u7a7a\u95f4\u590d\u6742\u5ea6\u5747\u4e3aO(N*V)\uff0c\u5176\u4e2d\u65f6\u95f4\u590d\u6742\u5ea6\u57fa\u672c\u5df2\u7ecf\u4e0d\u80fd\u518d\u4f18\u5316\u4e86\uff0c\u4f46\u7a7a\u95f4\u590d\u6742\u5ea6\u5374\u53ef\u4ee5\u4f18\u5316\u5230O(V)\u3002\u5148\u8003\u8651\u4e0a\u9762\u8bb2\u7684\u57fa\u672c\u601d\u8def\u5982\u4f55\u5b9e\u73b0\uff0c\u80af\u5b9a\u662f\u6709\u4e00\u4e2a\u4e3b\u5faa\u73afi=1..N\uff0c\u6bcf\u6b21\u7b97\u51fa\u6765\u4e8c\u7ef4\u6570\u7ec4f[i][0..V]\u7684\u6240\u6709\u503c\u3002\u90a3\u4e48\uff0c\u5982\u679c\u53ea\u7528\u4e00\u4e2a\u6570\u7ec4f[0..V]\uff0c\u80fd\u4e0d\u80fd\u4fdd\u8bc1\u7b2ci\u6b21\u5faa\u73af\u7ed3\u675f\u540ef[v]\u4e2d\u8868\u793a\u7684\u5c31\u662f\u6211\u4eec\u5b9a\u4e49\u7684\u72b6\u6001f[i][v]\u5462\uff1ff[i][v]\u662f\u7531f[i-1][v]\u548cf[i-1][v-c[i]]\u4e24\u4e2a\u5b50\u95ee\u9898\u9012\u63a8\u800c\u6765\uff0c\u80fd\u5426\u4fdd\u8bc1\u5728\u63a8f[i][v]\u65f6\uff08\u4e5f\u5373\u5728\u7b2ci\u6b21\u4e3b\u5faa\u73af\u4e2d\u63a8f[v]\u65f6\uff09\u80fd\u591f\u5f97\u5230f[i-1][v]\u548cf[i-1][v-c[i]]\u7684\u503c\u5462\uff1f\u4e8b\u5b9e\u4e0a\uff0c\u8fd9\u8981\u6c42\u5728\u6bcf\u6b21\u4e3b\u5faa\u73af\u4e2d\u6211\u4eec\u4ee5v=V..0\u7684\u987a\u5e8f\u63a8f[v]\uff0c\u8fd9\u6837\u624d\u80fd\u4fdd\u8bc1\u63a8f[v]\u65f6f[v-c[i]]\u4fdd\u5b58\u7684\u662f\u72b6\u6001f[i-1][v-c[i]]\u7684\u503c\u3002\u4f2a\u4ee3\u7801\u5982\u4e0b\uff1afor i=1..N for v=V..0 f[v]=max{f[v],f[v-c[i]]+w[i]};\u5176\u4e2d\u7684f[v]=max{f[v],f[v-c[i]]}\u4e00\u53e5\u6070\u5c31\u76f8\u5f53\u4e8e\u6211\u4eec\u7684\u8f6c\u79fb\u65b9\u7a0bf[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}\uff0c\u56e0\u4e3a\u73b0\u5728\u7684f[v-c[i]]\u5c31\u76f8\u5f53\u4e8e\u539f\u6765\u7684f[i-1][v-c[i]]\u3002\u5982\u679c\u5c06v\u7684\u5faa\u73af\u987a\u5e8f\u4ece\u4e0a\u9762\u7684\u9006\u5e8f\u6539\u6210\u987a\u5e8f\u7684\u8bdd\uff0c\u90a3\u4e48\u5219\u6210\u4e86f[i][v]\u7531f[i][v-c[i]]\u63a8\u77e5\uff0c\u4e0e\u672c\u9898\u610f\u4e0d\u7b26\uff0c\u4f46\u5b83\u5374\u662f\u53e6\u4e00\u4e2a\u91cd\u8981\u7684\u80cc\u5305\u95ee\u9898P02\u6700\u7b80\u6377\u7684\u89e3\u51b3\u65b9\u6848\uff0c\u6545\u5b66\u4e60\u53ea\u7528\u4e00\u7ef4\u6570\u7ec4\u89e301\u80cc\u5305\u95ee\u9898\u662f\u5341\u5206\u5fc5\u8981\u7684\u3002\u4e8b\u5b9e\u4e0a\uff0c\u4f7f\u7528\u4e00\u7ef4\u6570\u7ec4\u89e301\u80cc\u5305\u7684\u7a0b\u5e8f\u5728\u540e\u9762\u4f1a\u88ab\u591a\u6b21\u7528\u5230\uff0c\u6240\u4ee5\u8fd9\u91cc\u62bd\u8c61\u51fa\u4e00\u4e2a\u5904\u7406\u4e00\u4ef601\u80cc\u5305\u4e2d\u7684\u7269\u54c1\u8fc7\u7a0b\uff0c\u4ee5\u540e\u7684\u4ee3\u7801\u4e2d\u76f4\u63a5\u8c03\u7528\u4e0d\u52a0\u8bf4\u660e\u3002\u8fc7\u7a0bZeroOnePack\uff0c\u8868\u793a\u5904\u7406\u4e00\u4ef601\u80cc\u5305\u4e2d\u7684\u7269\u54c1\uff0c\u4e24\u4e2a\u53c2\u6570cost\u3001weight\u5206\u522b\u8868\u660e\u8fd9\u4ef6\u7269\u54c1\u7684\u8d39\u7528\u548c\u4ef7\u503c\u3002procedure ZeroOnePack(cost,weight) for v=V..cost f[v]=max{f[v],f[v-cost]+weight}\u6ce8\u610f\u8fd9\u4e2a\u8fc7\u7a0b\u91cc\u7684\u5904\u7406\u4e0e\u524d\u9762\u7ed9\u51fa\u7684\u4f2a\u4ee3\u7801\u6709\u6240\u4e0d\u540c\u3002\u524d\u9762\u7684\u793a\u4f8b\u7a0b\u5e8f\u5199\u6210v=V..0\u662f\u4e3a\u4e86\u5728\u7a0b\u5e8f\u4e2d\u4f53\u73b0\u6bcf\u4e2a\u72b6\u6001\u90fd\u6309\u7167\u65b9\u7a0b\u6c42\u89e3\u4e86\uff0c\u907f\u514d\u4e0d\u5fc5\u8981\u7684\u601d\u7ef4\u590d\u6742\u5ea6\u3002\u800c\u8fd9\u91cc\u65e2\u7136\u5df2\u7ecf\u62bd\u8c61\u6210\u770b\u4f5c\u9ed1\u7bb1\u7684\u8fc7\u7a0b\u4e86\uff0c\u5c31\u53ef\u4ee5\u52a0\u5165\u4f18\u5316\u3002\u8d39\u7528\u4e3acost\u7684\u7269\u54c1\u4e0d\u4f1a\u5f71\u54cd\u72b6\u6001f[0..cost-1]\uff0c\u8fd9\u662f\u663e\u7136\u7684\u3002\u6709\u4e86\u8fd9\u4e2a\u8fc7\u7a0b\u4ee5\u540e\uff0c01\u80cc\u5305\u95ee\u9898\u7684\u4f2a\u4ee3\u7801\u5c31\u53ef\u4ee5\u8fd9\u6837\u5199\uff1afor i=1..N ZeroOnePack(c[i],w[i]);\u521d\u59cb\u5316\u7684\u7ec6\u8282\u95ee\u9898\u6211\u4eec\u770b\u5230\u7684\u6c42\u6700\u4f18\u89e3\u7684\u80cc\u5305\u95ee\u9898\u9898\u76ee\u4e2d\uff0c\u4e8b\u5b9e\u4e0a\u6709\u4e24\u79cd\u4e0d\u592a\u76f8\u540c\u7684\u95ee\u6cd5\u3002\u6709\u7684\u9898\u76ee\u8981\u6c42\u201c\u6070\u597d\u88c5\u6ee1\u80cc\u5305\u201d\u65f6\u7684\u6700\u4f18\u89e3\uff0c\u6709\u7684\u9898\u76ee\u5219\u5e76\u6ca1\u6709\u8981\u6c42\u5fc5\u987b\u628a\u80cc\u5305\u88c5\u6ee1\u3002\u4e00\u79cd\u533a\u522b\u8fd9\u4e24\u79cd\u95ee\u6cd5\u7684\u5b9e\u73b0\u65b9\u6cd5\u662f\u5728\u521d\u59cb\u5316\u7684\u65f6\u5019\u6709\u6240\u4e0d\u540c\u3002\u5982\u679c\u662f\u7b2c\u4e00\u79cd\u95ee\u6cd5\uff0c\u8981\u6c42\u6070\u597d\u88c5\u6ee1\u80cc\u5305\uff0c\u90a3\u4e48\u5728\u521d\u59cb\u5316\u65f6\u9664\u4e86f[0]\u4e3a0\u5176\u5b83f[1..V]\u5747\u8bbe\u4e3a-\u221e\uff0c\u8fd9\u6837\u5c31\u53ef\u4ee5\u4fdd\u8bc1\u6700\u7ec8\u5f97\u5230\u7684f[N]\u662f\u4e00\u79cd\u6070\u597d\u88c5\u6ee1\u80cc\u5305\u7684\u6700\u4f18\u89e3\u3002\u5982\u679c\u5e76\u6ca1\u6709\u8981\u6c42\u5fc5\u987b\u628a\u80cc\u5305\u88c5\u6ee1\uff0c\u800c\u662f\u53ea\u5e0c\u671b\u4ef7\u683c\u5c3d\u91cf\u5927\uff0c\u521d\u59cb\u5316\u65f6\u5e94\u8be5\u5c06f[0..V]\u5168\u90e8\u8bbe\u4e3a0\u3002\u4e3a\u4ec0\u4e48\u5462\uff1f\u53ef\u4ee5\u8fd9\u6837\u7406\u89e3\uff1a\u521d\u59cb\u5316\u7684f\u6570\u7ec4\u4e8b\u5b9e\u4e0a\u5c31\u662f\u5728\u6ca1\u6709\u4efb\u4f55\u7269\u54c1\u53ef\u4ee5\u653e\u5165\u80cc\u5305\u65f6\u7684\u5408\u6cd5\u72b6\u6001\u3002\u5982\u679c\u8981\u6c42\u80cc\u5305\u6070\u597d\u88c5\u6ee1\uff0c\u90a3\u4e48\u6b64\u65f6\u53ea\u6709\u5bb9\u91cf\u4e3a0\u7684\u80cc\u5305\u53ef\u80fd\u88ab\u4ef7\u503c\u4e3a0\u7684nothing\u201c\u6070\u597d\u88c5\u6ee1\u201d\uff0c\u5176\u5b83\u5bb9\u91cf\u7684\u80cc\u5305\u5747\u6ca1\u6709\u5408\u6cd5\u7684\u89e3\uff0c\u5c5e\u4e8e\u672a\u5b9a\u4e49\u7684\u72b6\u6001\uff0c\u5b83\u4eec\u7684\u503c\u5c31\u90fd\u5e94\u8be5\u662f-\u221e\u4e86\u3002\u5982\u679c\u80cc\u5305\u5e76\u975e\u5fc5\u987b\u88ab\u88c5\u6ee1\uff0c\u90a3\u4e48\u4efb\u4f55\u5bb9\u91cf\u7684\u80cc\u5305\u90fd\u6709\u4e00\u4e2a\u5408\u6cd5\u89e3\u201c\u4ec0\u4e48\u90fd\u4e0d\u88c5\u201d\uff0c\u8fd9\u4e2a\u89e3\u7684\u4ef7\u503c\u4e3a0\uff0c\u6240\u4ee5\u521d\u59cb\u65f6\u72b6\u6001\u7684\u503c\u4e5f\u5c31\u5168\u90e8\u4e3a0\u4e86\u3002\u8fd9\u4e2a\u5c0f\u6280\u5de7\u5b8c\u5168\u53ef\u4ee5\u63a8\u5e7f\u5230\u5176\u5b83\u7c7b\u578b\u7684\u80cc\u5305\u95ee\u9898\uff0c\u540e\u9762\u4e5f\u5c31\u4e0d\u518d\u5bf9\u8fdb\u884c\u72b6\u6001\u8f6c\u79fb\u4e4b\u524d\u7684\u521d\u59cb\u5316\u8fdb\u884c\u8bb2\u89e3\u3002\u5c0f\u7ed301\u80cc\u5305\u95ee\u9898\u662f\u6700\u57fa\u672c\u7684\u80cc\u5305\u95ee\u9898\uff0c\u5b83\u5305\u542b\u4e86\u80cc\u5305\u95ee\u9898\u4e2d\u8bbe\u8ba1\u72b6\u6001\u3001\u65b9\u7a0b\u7684\u6700\u57fa\u672c\u601d\u60f3\uff0c\u53e6\u5916\uff0c\u522b\u7684\u7c7b\u578b\u7684\u80cc\u5305\u95ee\u9898\u5f80\u5f80\u4e5f\u53ef\u4ee5\u8f6c\u6362\u621001\u80cc\u5305\u95ee\u9898\u6c42\u89e3\u3002\u6545\u4e00\u5b9a\u8981\u4ed4\u7ec6\u4f53\u4f1a\u4e0a\u9762\u57fa\u672c\u601d\u8def\u7684\u5f97\u51fa\u65b9\u6cd5\uff0c\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\u7684\u610f\u4e49\uff0c\u4ee5\u53ca\u6700\u540e\u600e\u6837\u4f18\u5316\u7684\u7a7a\u95f4\u590d\u6742\u5ea6\u3002
\u5f00\u5fc3\u7684\u91d1\u660e\uff1a
pascal\u6e90\u7a0b\u5e8f\uff1a
program aaa;
var
v,p:array [1..60] of longint;{v:\u4ef7\u503c\uff0cp\uff1a\u91cd\u91cf}
f:array [0..60,0..32000] of longint;
i,j,n,m:longint;
function max(a,b:longint):longint;
begin
if a>b then max:=a
else max:=b;
end;
begin
readln(n,m);
fillchar(q,sizeof(q),false);
for i:=1 to m do
readln(v[i],p[i]\uff09\uff1b
for i:=1 to m do
for j:=0 to n do
begin
if (v[i]<=j) then
f[i,j]:=max(f[i-1,j],f[i-1,j-v[i]]+v[i]*p[i]){\u52a8\u6001\u89c4\u5212\u8f6c\u79fb\u65b9\u7a0b}
else f[i,j]:=f[i-1,j];
end;
writeln(f[m,n]);
end.
在历届NOIP竞赛中，有4道初赛题和5道复赛题均涉及到背包问题，所谓的背包问题，可以描述如下：一个小偷打劫一个保险箱，发现柜子里有N类不同大小与价值的物品，但小偷只有一个容积为M的背包来装东西，背包问题就是要找出一个小偷选择所偷物品的组合，以使偷走的物品总价值最大。
如有4件物品，容积分别为： 3 4 5 8
对应的价值分别为： 4 5 7 10
小偷背包的载重量为：12
则取编号为1 2 3的物品，得到最大价值为16。
算法分析：如果采用贪心法，则先取价值最大的10，消耗了容积8，下面只能取容积为4的物品，得到价值5，这样总价值是15，这不是最优解，因此贪心法是不正确的。
采用穷举法，用一个B数组来表示取数的标记，当B[i]=0时表示第i件物品不取，当B[i]=1时表示第i件物品已取，初始化全部取0，以下算法是从后面的物品开始取起，通过B数组的取值把15种取法全部穷举出来，价值MAX初始化为0。
B[0] B[1] B[2] B[3] B[4]
0 0 0 0 0 {初始化}
0 0 0 0 1 {取第4件物品，容积为8，不超，价值为10，将MAX替换为10}
0 0 0 1 0 ｛取物品3，容积为5，不超，价值为7，不换｝
0 0 0 1 1 ｛取物品3、4，容积为13，超｝
0 0 1 0 0 ｛取物品2，容积为4，不超，价值为5，不换｝
0 0 1 0 1
0 0 1 1 0
0 0 1 1 1
……
0 1 1 1 0 ｛这是最佳方案｝
0 1 1 1 1
1 0 0 0 0 ｛当B〔0〕＝1时停止，B〔0〕称为哨兵｝
生成B数组中数据的方法如下：
fillchar(b,sizeof(b),0);
while b[0]=0 do
begin j:=n;
while b[j]=1 do dec(j);
b[j]:=1;
for i:=j+1 to n do
b[i]:=0;
end；
小结：以上每件物品只能取1件，所以取法只有0和1两种情况，我们称之为0、1背包，算法的时间复杂度为O（2N），在1秒内N只能做到20。
例1：选数（NOIP2002 初中组复赛第2题）
[问题描述]:已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：
3＋7＋12=22 3＋7＋19＝29 7＋12＋19＝38 3＋12＋19＝34。
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：3＋7＋19＝29。
[输入]：
键盘输入，格式为：
n , k （1<=n<=20，k＜n）
x1,x2，…,xn （1<=xi<=5000000）
n[输出]：
屏幕输出，格式为：
一个整数（满足条件的种数）。
[输入输出样例]:
输入：
4 3
3 7 12 19
输出：
1
[算法分析]:本题应用背包问题中取数的方法进行穷举，在取数的过程中，当B数组中有K个1的时候将对应的K个数相加，再判断是不是素数。
主要程序段如下：
readln(n,k); sum:=0;
for i:=1 to n do read(a[i]);
fillchar(b,sizeof(b),0);
while b[0]=0 do
begin j:=n;
while b[j]=1 do dec(j);
b[j]:=1;
for i:=j+1 to n do b[i]:=0;
m:=0;
for i:=1 to n do
if b[i]=1 then m:=m+1; {统计1的个数}
if m=k then
begin 计算此种取数方法得到的和S；
if S 是素数 then sum:=sum+1;
end;
end;
例2：采药(NOIP2005 初中组复赛第3题)
【问题描述】
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
【输入文件】
输入文件medic.in的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
【输出文件】
输出文件medic.out包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
【样例输入】
70 3
71 100
69 1
1 2
【样例输出】
3
【数据规模】
对于30%的数据，M <= 10；
对于全部的数据，M <= 100。
【算法分析】本题如果采用上述方法来解，只能将M算到20，而这里M〈=100，所以只能拿30%的分数，比较好的算法是采用动态规划，为了能说清算法，现重新举一个例子，若输入：
10 3
3 4
4 5
5 6
表示背包的容量是10，有3种物品。用一个数组用来表示背包容量与其最大价值的关系，上例中设置一个数组count,用下标表示容量，初始化为0。然后按物品的顺序一一来统计此时的最大价值，每种药品对应各种背包容量时得到的最大价值为：
对于是第i件物品，背包容量为j时的最大价值Cmax(j)=MAX(Cmaxj,Pi+余下空间的最大价值Cmax(j-i物品所占的空间))，如上例中，根据物品的不断增加，各容量背包得到的最大价值不断替换：
容量 1 2 3 4 5 6 7 8 9 10
价值
序号 0 0 0 0 0 0 0 0 0 0
1 0 0 4 4 4 4 4 4 4 4
2 0 0 4 5 5 5 9 9 9 9
3 0 0 4 5 6 6 9 10 11 11
[数据结构] time,price数组分别用来存入时间和价值，count来存入背包的价值。
var
time,price:array[1..100] of longint;
t:longint; i,m,j:integer;
count:array[0..1000] of longint;
begin
assign(input,'medic.in');
assign(output,'medic.out');
reset(input);
rewrite(output);
readln(t,m);
for i:=1 to m do
readln(time[i],price[i]);
fillchar(count,sizeof(count),0);
for i:=1 to m do
for j:=t downto 1 do
begin
if (j>=time[i]) and (price[i]+count[j-time[i]]>count[j]) then
count[j]:=price[i]+count[j-time[i]];
end; {j>=time[i]表示当前的容量能放入背包，price[i]+count[j-time[i]]>count[j]表示第i件物品的价值加上第i件物品对于背包容量为j时余下空间的最大价值大于当前背包容量为j时的最大价值}
writeln(count[t]);
close(input);
close(output);
end.
例3：开心的金明（NOIP2006 初中组复赛第2题）
题目较长，省略，本题与例2相比，在比较时要先将价值乘以一个数，其余一样，但要注意的是：本题N的范围是<=26，如果用0、1背包穷举法在1秒内只能过10个点中的8个点。
总结：采用动态规划的时间复杂度为O(n*m)，范围比穷举法大多了，但也有弱点，当数据不是整数时，就不可使用；如果还要求出具体的取法，那也相当麻烦。
DP,0-1背包问题.
把总钱数看作背包可容重量.
把希望购买物品的个数看作要放进背包的物品的数量.
把物品的价格看作物品的重量.
把物品的价格与物品的重要度的乘积看作物品的价值.
i:前i个物品 j:背包剩余可容重量 w:第i个物品的重量 r:第i个物品的价值
i=0 f[i,j]=0
i>0 f[i,j]=max{f[i-1,j],f[i-1,j-w]+r}
program happy(input,output);
var
i,j,m,n:longint;
w,r:array[1..25] of longint;
a:array[0..1,-10000..100000] of longint;
begin
assign(input,'happy.in');reset(input);
assign(output,'happy.out');rewrite(output);
read(n,m);
for i:=1 to m do
begin
read(w,r);
r:=r*w;
end;
for i:=1 to m do
begin
a[1]:=a[0];
for j:=w to n do
if a[0,j-w]+r>a[1,j] then a[1,j]:=a[0,j-w]+r;
a[0]:=a[1];
end;
writeln(a[1,n]);
close(input);close(output);
end.
(参见经典0-1背包-采药)
把0-1背包问题一改就行了 只是把加的 重量 改成 价值与重要度的乘积 ！
program happy;
var
f:array[0..25,0..30000] of longint;
i,j:integer;
n,m:longint;
v,p:array[1..25] of longint;
begin
readln(m,n);
for i:=1 to n do
read(v[i],p[i]);
fillchar(f,sizeof(f),0);
for i:=1 to n do
for j:=1 to m do
begin
f[i,j]:=f[i-1,j];
if (j>=v[i])and(f[i,j]<f[i-1,j-v[i]]+p[i]*v[i]) then
f[i,j]:=f[i-1,j-v[i]]+p[i]*v[i];
end;
writeln(f[n,m]);
end.
典型的01背包问题，时间复杂度为O(Nm)。
一种做法是使用滚动数组，每次可以从前往后更新，也可以从后往前更新；另一种是只使用一个一维数组，每次只能从后往前更新。
在表示状态的时候，可以用f[i]表示正好花了i元，能够得到的最大总和；也可以用f[i]表示花了不超过i元，能够得到的最大总和。
程序1：滚动数组+表示正好
var
n,m,i,j,ans:longint;
a:array[0..25,0..2] of longint;
dp,dp2:array[0..30000] of longint;
begin
assign(input,'happy.in'); reset(input);
assign(output,'happy.out'); rewrite(output);
fillchar(a,sizeof(a),0);
read(n,m);
for i:=1 to m do begin
read(a[i,0],a[i,1]); {输入价格和重要程度}
a[i,2]:=a[i,0]*a[i,1]; {计算乘积}
end;
fillchar(dp2,sizeof(dp2),$FF); {初始时dp[i]=-1，i>0，表示正好花i元得不到任何总和}
dp2[0]:=0; {只有dp[0]=0，因为正好花了0元，得到的总和为0}
for i:=1 to m do begin
dp:=dp2; {以后用dp来推dp2}
for j:=0 to n do {枚举花了j元钱}
if (dp[j]>-1) and (j+a[i,0]<=n) and (dp2[j+a[i,0]]<dp[j]+a[i,2]) then {j元钱的方案存在，加上这次的价格没有超过可用的n元，并且这个方案得到的总和更大，就更新}
dp2[j+a[i,0]]:=dp[j]+a[i,2];
end;
ans:=-1; {求dp2中的最大值}
for i:=0 to n do
if dp2[i]>ans then ans:=dp2[i];
writeln(ans);
close(input); close(output);
end.
程序2：单个一维数组+表示不超过
var
n,m,i,j:longint;
a:array[0..25,0..2] of longint;
dp:array[0..30000] of longint;
begin
assign(input,'happy.in'); reset(input);
assign(output,'happy.out'); rewrite(output);
fillchar(a,sizeof(a),0);
read(n,m);
for i:=1 to m do begin
read(a[i,0],a[i,1]); {输入价格和重要程度}
a[i,2]:=a[i,0]*a[i,1]; {计算乘积}
end;
fillchar(dp,sizeof(dp),0); {初始时dp[i]=0，表示花不超过i元可以得到0总和}
for i:=1 to m do
for j:=n downto 0 do {从后往前枚举花了j元钱}
if (j+a[i,0]<=n) and (dp[j+a[i,0]]<dp[j]+a[i,2]) then {加上这次的价格没有超过可用的n元，并且这个方案得到的总和更大，就更新}
dp[j+a[i,0]]:=dp[j]+a[i,2];
writeln(dp[n]); {输出最后花不超过n元能得到的最大总和}
close(input); close(output);
end.
绛旓細灏忕粨锛氫互涓婃瘡浠剁墿鍝佸彧鑳藉彇1浠讹紝鎵浠ュ彇娉曞彧鏈0鍜1涓ょ鎯呭喌锛屾垜浠О涔嬩负0銆1鑳屽寘锛岀畻娉曠殑鏃堕棿澶嶆潅搴︿负O锛2N锛夛紝鍦1绉掑唴N鍙兘鍋氬埌20銆備緥1锛氶夋暟锛圢OIP2002 鍒濅腑缁勫璧涚2棰橈級[闂鎻忚堪]:宸茬煡 n 涓暣鏁 x1,x2,鈥,xn锛屼互鍙婁竴涓暣鏁 k锛坘锛渘锛夈備粠 n 涓暣鏁颁腑浠婚 k 涓暣鏁扮浉鍔狅紝鍙垎鍒緱鍒颁竴...
绛旓細program happy(input,output);const maxn=30001;maxm=25;var a:array[0..maxn]of longint;v,w:array[0..maxm]of longint;n,m,i,j:longint;procedure readdata;begin assign(input,'happy.in');reset(input);readln(n,m);for i:=1 to m do begin readln(v[i],w[i]);end;clo...
绛旓細鍛婅瘔鎴戜綘鐨勯偖绠憋紝鎴戠粰浣犲彂杩囧幓 闄堕櫠鎽樿嫻鏋 寮蹇冪殑閲戞槑 jam鐨勮鏁版硶 寰幆 涔熷彲鍒皁ifans涓婂幓涓嬭浇 鍙傝冭祫鏂欙細noip 缁勫浼
绛旓細浣犵殑杩欓亾棰樼洰涓嶆槸鎻愰珮缁勭殑鈥滈噾鏄庣殑棰勭畻鏂规鈥濓紝鑰屾槸鏅強缁鐨勨寮蹇冪殑閲戞槑鈥濆紑蹇冪殑閲戞槑鍏跺疄寰堢畝鍗曪紝灏辨槸01鑳屽寘鐣ュ井鏀逛竴涓嬶紝浣犵湅浠ｇ爜鍚 var f:Array[1..30001]of longint;i,x,m,n,w,c:longint;function max(x,y:longint):longint;begin if x>y then exit(x) else exit(y);end;begin ...
绛旓細锛圢OIP2006鏅強缁锛夌珵璧涙椂闂达細2006骞11鏈18鏃 涓嬪崍1:30-4:30 璇曢鍚嶇О random Happy count sequence 鐩綍 random Happy count sequence 杈撳叆鏂囦欢鍚 random.in happy.in count.in sequence.in 杈撳嚭鏂囦欢鍚 random.out happy.out count.out sequence.out 璇曢绫诲瀷 闈炰氦浜掑紡绋嬪簭棰 闈炰氦浜掑紡绋嬪簭棰 闈炰氦浜...
绛旓細1锛夎儗鍖呯被锛01骞鏅強缁銆婅绠遍棶棰樸嬨05鏅強缁勩婇噰鑽,06骞存櫘鍙婄粍銆寮蹇冪殑閲戞槑銆嬨06骞存彁楂樼粍銆婇噾鏄庣殑棰勭畻鏂规銆嬶級2锛夌畝鍗曟爲鐘讹紙03骞淬婂姞鍒嗕簩鍙夋爲銆嬶級3锛夋渶闀縓X瀛愬簭鍒楋紙04骞存彁楂樼粍銆婂悎鍞遍槦褰嬨99骞存彁楂樼粍銆婃嫤鎴寮广嬶級4锛夌煩闃佃繛涔&鐭冲瓙褰掑苟锛06骞存彁楂樼粍銆婅兘閲忛」閾俱嬶級5锛夊渾鐜彇鏁扮被锛03骞...
绛旓細瀹炲湪鎯充笉璧锋潵鍙互鍏堢湅棰樿В,鍘荤悊瑙ｄ汉瀹剁殑鎬濇兂涔嬪悗,涓嶈鐪嬫爣绋嬫妸绋嬪簭鍋氬嚭鏉モ︹3銆佹敞鎰忔暟缁勪笉瑕佸紑鐨勮繃灏,涓鑸兘鏄乏鍙抽兘寮澶т竴鐐,姣斿浠栫殑鏁版嵁鑼冨洿鏄1~100 ,鏁扮粍灏卞紑0~101.杩欎釜鏄槻瓒婄晫鐨,鍥犱负寰堝DP璧嬪垵鍊肩殑鏃跺欎細鐢ㄥ埌F[0],F[0,0]4銆佸垵濮嬪艰姝ｇ‘,鍥犱负寰堝DP鍏朵粬鍦版柟閮芥槸姝ｇ‘鐨勫洜涓哄垵濮嬪艰祴閿欎簡鑰屽叏閮...
