var
i,j,n,m,l,k:longint;
a,b,f:array[1..30000] of longint;
begin
readln(m,n);
for i:=1 to n do
begin
readln(a[i],b[i]);
b[i]:=b[i]*a[i];
end;
for i:=1 to n do
for j:=m downto 1 do
if j>a[i] then
begin
if f[j]<f[j-a[i]]+b[i] then
f[j]:=f[j-a[i]]+b[i];
end;
writeln(f[m]);
end.

测试数据 #0: Accepted, time = 0 ms, mem = 552 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 556 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 548 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 552 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 552 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 552 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 556 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 552 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 556 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 556 KiB, score = 10
Accepted, time = 0 ms, mem = 556 KiB, score = 100
发个C语言的秒杀
###Block code
#include<stdio.h>
int i,j,p[30],v[30],n,m,f[30010];
int main()
{
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++)
scanf("%d %d",&v[i],&p[i]);
for(i=1;i<=m;i++)
for(j=n;j>=v[i];j--)
if(f[j-v[i]]+v[i]*p[i]>f[j])
f[j]=f[j-v[i]]+v[i]*p[i];
for(i=1;i<=n;i++)
if(f[i]>f[0])
f[0]=f[i];
printf("%d",f[0]);
//getch();

return 0;
}

测试数据 #0: Accepted, time = 0 ms, mem = 552 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 556 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 548 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 552 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 552 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 552 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 556 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 552 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 556 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 556 KiB, score = 10
Accepted, time = 0 ms, mem = 556 KiB, score = 100
发个C语言的秒杀
#include<stdio.h>
int i,j,p[30],v[30],n,m,f[30010];
int main()
{
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++)
scanf("%d %d",&v[i],&p[i]);
for(i=1;i<=m;i++)
for(j=n;j>=v[i];j--)
if(f[j-v[i]]+v[i]*p[i]>f[j])
f[j]=f[j-v[i]]+v[i]*p[i];
for(i=1;i<=n;i++)
if(f[i]>f[0])
f[0]=f[i];
printf("%d",f[0]);
//getch();

return 0;
}

#include<cstdio>
#include<algorithm>
using namespace std;
#define IOFileName "P1317"
const int maxn=30002;
int n,m,v,p,map[maxn]={0};
int main(){
//freopen(IOFileName".in","r",stdin);
//freopen(IOFileName".out","w",stdout);
scanf("%d %d\n",&n,&m);
for(int i=0;i<m;i++){
scanf("%d %d\n",&v,&p);
for(int j=n;j>=0;j--){
if((map[j]&&j+v<=n)||j==0){
map[j+v]=max(map[j+v],map[j]+v*p);
}
}
}
printf("%d\n",*max_element(map,map+n+1));
}

就是01背包问题，把medic的T和M的取值范围该了一下，然后输入改了一下。消耗c就是题目中叙述的v，而价值v就是题目v*p

var i,j,n,m,l,k:longint;
a,b,f:array[1..30000] of longint;
begin
readln(m,n);
for i:=1 to n do begin readln(a[i],b[i]); b[i]:=b[i]*a[i]; end;
for i:=1 to n do
for j:=m downto 1 do
if j>a[i] then begin if f[j]<f[j-a[i]]+b[i] then f[j]:=f[j-a[i]]+b[i]; end;
writeln(f[m]);
end.

var
n,m,i,j:longint;
w,v,f:array[-1..100000] of int64;
function max(a,b:int64):int64;
begin
if a>b then exit(a) else exit(b);
end;
begin
readln(m,n);
for i:=1 to n do
read(w[i],v[i]);
fillchar(f,sizeof(f),0);
for i:=1 to n do
for j:=m downto 1 do
if j>=w[i] then f[j]:=max(f[j-w[i]]+w[i]*v[i],f[j]);
writeln(f[m]);
end.

尼玛数组开小了点就错了一个点。我的AC率啊。。
难题跪也就算了，这题目还提交两次。。
program jm;
var buy:array[0..50000] of longint;
n,m,i,j,a,b,k,max,result:longint;
begin
readln(n,m);max:=1;
for i:=1 to 30001 do buy[i]:=-1;
for i:=1 to m do
begin
readln(a,b);
k:=trunc(a*b);
for j:=n downto 0 do
if ((buy[j]>=0) and (buy[j+a]<buy[j]+k)) then buy[j+a]:=buy[j]+k;
end;
result:=0;
for i:=n downto 0 do
if buy[i]>result then result:=buy[i];
writeln(result);
end.

用时30ms 不算完美

=皿= 这题难度竟然是3 ( >ρ < ”)
01背包=.=

测试数据 #0: Accepted, time = 0 ms, mem = 656 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 660 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 656 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 660 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 660 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 660 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 660 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 660 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 660 KiB, score = 10

测试数据 #9: Accepted, time = 0 ms, mem = 656 KiB, score = 10
#include<stdio.h>
int valu[1005];
int volu[1005];
int f[30005];
int main()
{
int a;
int i,j,n,volume;
scanf("%d%d",&volume,&n);
for(i=0; i<n; i++)
{
scanf("%d",&volu[i]);
scanf("%d",&a);
valu[i]=volu[i]*a;
}
for(i=0; i<=volume; i++)f[i]=0;
for(i=0; i<n; i++)
for(j=volume; j>=0; j--) //pay sttention to the SignofEquality
if(j-volu[i]>=0)f[j]=f[j-volu[i]]+valu[i]>f[j]?f[j-volu[i]]+valu[i]:f[j];
printf("%d\n",f[volume]);

}

0ms秒杀。。。
#include <iostream>
using namespace std;
#define M 30
#define N 30005

typedef long long ll;

int n, m;
ll v[M], p[M];
ll f[N];

int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>v[i]>>p[i];
for(int i=1;i<=m;i++)
for(int j=n;j>=0;j--)
if(j>=v[i])
f[j]=max(f[j],f[j-v[i]]+p[i]*v[i]);
cout<<f[n];

return 0;
}

经典的背包啊

点这里查看程序源码+详细题解

f[j]:=max(f[j],f[j-v[i]]+p[i]*v[i]);

恶心的动态。。

编译通过...

├ 测试数据 01：答案正确... (0ms, 696KB)

├ 测试数据 02：答案正确... (0ms, 696KB)

├ 测试数据 03：答案正确... (0ms, 696KB)

├ 测试数据 04：答案正确... (0ms, 696KB)

├ 测试数据 05：答案正确... (0ms, 696KB)

├ 测试数据 06：答案正确... (0ms, 696KB)

├ 测试数据 07：答案正确... (0ms, 696KB)

├ 测试数据 08：答案正确... (0ms, 696KB)

├ 测试数据 09：答案正确... (0ms, 696KB)

├ 测试数据 10：答案正确... (0ms, 696KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 0ms / 696KB

朴素背包……

终于明白了什么是动态规划，朴素的0/1背包应该算掌握了，以下是我写的个人认为还算清晰的算法，这道题的题目描述中变量名换来换去的好晕，所以我都加了注释。

#include

using namespace std;

const int m_max = 25; //物品数量上限

typedef struct object //定义物品结构体

{

int v, p, w; //v=价格，p=重要度，w=v*p权值

void getw() //求权值w

{

w = v * p;

}

};

int max(const int a, const int b)

{

return a > b ? a : b;

}

int n, m; //n=总钱数，m=物品数

object j[m_max]; //物品信息

int pack(const int money, const int i)

{

if (i == 0)

{

if (j[i].v > money)

return 0;

else

return j[i].w;

}

if (j[i].v > money)

return pack(money, i-1);

else

return max(pack(money, i-1), pack(money - j[i].v, i-1) + j[i].w);

}

int main()

{

scanf("%d%d", &n, &m);

for (int i_m = 0; i_m < m; i_m++)

{

scanf("%d%d", &(j.v), &(j.p));

j.getw();

}

printf("%d\n", pack(n, m-1));

}

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

点击查看代码

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var f:array[0..30000] of longint;

w,s,c:array[1..25] of longint;

i,j,n,m:longint;

function max(x,y:longint):longint;

begin

if x>y then max:=x else max:=y;

end;

begin

readln(m,n);

for i:=1 to n do begin

readln(w[i],s[i]);

c[i]:=w[i]*s[i];

end;

for i:=1 to m do begin

f[i]:=0;

end;

for i:=1 to n do begin

for j:=m downto 1 do begin

if j>=w[i] then f[j]:=max(f[j-w[i]]+c[i],f[j]);

end;

end;

writeln(f[m]);

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

program ex;

var f:array[0..25,0..30000] of longint;

w,c:array[1..25] of longint;

i,j,n,m:longint;

function max(x,y:longint):longint;

begin

if x>y then max:=x else max:=y;

end;

begin

readln(n,m);

for i:=1 to m do

begin

readln(w[i],c[i]);

c[i]:=w[i]*c[i];

end;

for i:=1 to m do

for j:=1 to n do

if j>=w[i] then f:=max(f+c[i],f)

else f:=f;

writeln(f[m,n]);

end.

第十题纪念

var

n,m,i,j,a:longint;

f:array[0..30000] of longint;

v,w:array[1..30] of longint;

begin

readln(n,m);

for i:=1 to m do

begin

readln(v[i],a);

w[i]:=v[i]*a;

end;

fillchar(f,sizeof(f),0);

for i:=1 to m do

for j:=n downto v[i] do

if f[j]