#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int n,m,v[30],p[30],f[30005];
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;i ++)scanf("%d%d",&v[i],&p[i]);
for(int i = 1;i <= m;i ++){
for(int j = n;j >=0;j --){
f[j] = j >= v[i] ? max(f[j - v[i]] + p[i] * v[i],f[j]) : f[j];
}
}
printf("%d",f[n]);

return 0;
}

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 1340 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1344 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1340 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1340 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1340 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1340 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1340 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 1344 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 1340 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 1336 KiB, score = 10
Accepted, time = 15 ms, mem = 1344 KiB, score = 100

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
long long n,m,w[30],c[30],dp[100000];
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>w[i]>>c[i];
for(int i=1;i<=m;i++)
{
for(int j=n;j>=w[i];j--)
{
dp[j]=max(dp[j],dp[j-w[i]]+c[i]*w[i]);
}
}
cout<<dp[n]<<endl;
return 0;
}

Accepted like a cork.

转化成01背包问题
递推 滚动数组
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int d[30000+3];
int main(){
int n,m;
cin>>n>>m;
memset(d,0,sizeof(d));
int v,w;
for(int i=1;i<=m;i++){
scanf("%d%d",&v,&w);w=v*w;
for(int j=n;j>=0;j--){
if(j>=v) d[j]=max(d[j],d[j-v]+w);

}
}
cout<<d[n];
return 0;
}

#include <iostream>
using namespace std;
const int MAXM=30;
const int MAXV=30010;
int dp[MAXM][MAXV];
int vi[MAXM],pi[MAXM];
int main()
{
int m,v;
cin>>v>>m;
for(int i=1;i<=m;i++)
{
cin>>vi[i]>>pi[i];
pi[i]*=vi[i];
}
for(int i=1;i<=m;i++)
for(int j=0;j<=v;j++)
{
if(j<vi[i])
dp[i][j]=dp[i-1][j];
else
dp[i][j]=max(dp[i-1][j],dp[i-1][j-vi[i]]+pi[i]);
}
cout<<dp[m][v]<<endl;
return 0;

}

#include <cstdio>
#include <iostream>
using std::max;

int main(void){
freopen("in.txt","r",stdin);
int n,maxm;
int c[30],w[30];
int f[30020]={0};
scanf("%d%d",&maxm,&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&c[i],&w[i]);
w[i]*=c[i];
}
for(int i=1;i<=n;i++)\
for(int j=maxm;j>=c[i];j--)
f[j]=max(f[j-c[i]]+w[i],f[j]);
printf("%d",f[maxm]);
return 0;
}

#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int n,m,v[30],p[30],f[30005];
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;i ++)scanf("%d%d",&v[i],&p[i]);
for(int i = 1;i <= m;i ++){
for(int j = n;j >=0;j --){
f[j] = j >= v[i] ? max(f[j - v[i]] + p[i] * v[i],f[j]) : f[j];
}
}
printf("%d",f[n]);

return 0;
}

#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int n,m,v[30],p[30],f[30][30005];
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;i ++)scanf("%d%d",&v[i],&p[i]);
for(int i = 1;i <= m;i ++){
for(int j = n;j >=0;j --){
f[i][j] = j >= v[i] ? max(f[i -1][j - v[i]] + p[i] * v[i],f[i - 1][j]) : f[i - 1][j];
}
}
printf("%d",f[m][n]);

return 0;
}

#include <cstdio>

using namespace std;

inline int max(int a,int b) {
return a>b?a:b;
}

int main(void) {
int n=0,v=0;
scanf("%d %d",&v,&n);
int w[n],c[n];
for (int i=0;i<n;++i) {
int temp=0;
scanf("%d %d",c+i,&temp);
w[i]=temp*c[i];
}
int f[v+1];
for (int i=0;i<=v;++i)
f[i]=0;
for (int i=0;i<n;++i)
for (int j=v;j>=0;--j)
if (j>=c[i])
f[j]=max(f[j],f[j-c[i]]+w[i]);
int ans=0;
for (int i=0;i<v+1;++i)
if (f[i]>ans)
ans=f[i];
printf("%d\n",ans);
return 0;
}
QwQ我好菜

评测状态 Accepted
题目 P1317 开心的金明
递交时间 2015-10-09 17:29:42
代码语言 Pascal
评测机 VijosEx
消耗时间 177 ms
消耗内存 24248 KiB
评测时间 2015-10-09 17:29:43
评测结果
编译成功

Free Pascal Compiler version 2.6.4 [2014/03/06] for i386
Copyright (c) 1993-2014 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(12,32) Warning: Variable "f" does not seem to be initialized
Linking foo.exe
13 lines compiled, 0.1 sec , 29824 bytes code, 1628 bytes data
1 warning(s) issued
测试数据 #0: Accepted, time = 6 ms, mem = 24248 KiB, score = 10
测试数据 #1: Accepted, time = 19 ms, mem = 24248 KiB, score = 10
测试数据 #2: Accepted, time = 20 ms, mem = 24248 KiB, score = 10
测试数据 #3: Accepted, time = 20 ms, mem = 24248 KiB, score = 10
测试数据 #4: Accepted, time = 31 ms, mem = 24248 KiB, score = 10
测试数据 #5: Accepted, time = 3 ms, mem = 24248 KiB, score = 10
测试数据 #6: Accepted, time = 16 ms, mem = 24248 KiB, score = 10
测试数据 #7: Accepted, time = 16 ms, mem = 24244 KiB, score = 10
测试数据 #8: Accepted, time = 31 ms, mem = 24248 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 24248 KiB, score = 10
Accepted, time = 177 ms, mem = 24248 KiB, score = 100
代码
var n,m,i,j:longint;
w,v,f:array[-1..1000000]of int64;
function max(x,y:int64):int64;
begin
if x>y then max:=x else max:=y;
end;
begin
readln(m,n);
for i:=1 to n do readln(w[i],v[i]);
for i:=1 to n do
for j:=m downto 1 do
if j>=w[i] then f[j]:=max(f[j],f[j-w[i]]+w[i]*v[i]);
writeln(f[m]);
end.

呵呵，第六遍…………………………………………………………………………………………………………………………，终于过了，太煎熬了，各位注意很容易就超时
！！！！！！！被坑了好几次！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

#include <iostream>
#include <cstdio>

using namespace std;
int f[30][30005],i,j,k,n,m,l,v[30],w[30];
int main()
{
cin >>n>>m;
for (i=1;i<=m;i++)
cin >>v[i]>>w[i];
for (i=1;i<=m;i++)
for (j=0;j<=n;j++)
if (j>v[i])
{
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+v[i]*w[i]);
}
else f[i][j]=f[i-1][j];
cout <<f[m][n];
}

var n,m,i,j:longint;
v,p:array[1..25] of longint;
a:array[0..25,0..30000] of longint;
function max(b,c:longint):longint;
begin
if b>c then exit(b) else exit(c)
end;
begin
read(m,n);
for i:=1 to n do
read(v[i],p[i]);
for i:=1 to n do
for j:=1 to m do
if j>=v[i] then a[i,j]:=max(a[i-1,j],a[i-1,j-v[i]]+v[i]*p[i])
else a[i,j]:=a[i-1,j];

write(a[n,m])
end.

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

const int MAXN = 30010;
const int MAXM = 32;

int bp[MAXM][MAXN], v[MAXM], w[MAXM];

int main()
{
#ifdef OFFLINE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif

memset(bp, 0, sizeof(bp));
memset(v, 0, sizeof(v));
memset(w, 0, sizeof(w));

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

for (int i = 1; i <= m; i++)
scanf("%d%d", &v[i], &w[i]);

for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (v[i] <= j)
bp[i][j] = max(bp[i - 1][j], bp[i - 1][j - v[i]] + v[i] * w[i]);
else
bp[i][j] = bp[i - 1][j];

int maxnum = 0;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
maxnum = max(maxnum, bp[i][j]);

printf("%d\n", maxnum);

return 0;
}

测试数据 #0: Accepted, time = 0 ms, mem = 364 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 364 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 368 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 364 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 368 KiB, score = 10
Accepted, time = 15 ms, mem = 368 KiB, score = 100
代码
#include <iostream>
#include <cstring>

#define MAX(A,B) A>B?A:B

using namespace std;

struct Item{
int itemPrice;
int itemValue;
};

int main(){
int totalMoney,itemNum;
int value[30001];
memset(value, 0, 30001*sizeof(int));
Item item[26];
cin >> totalMoney >> itemNum;
for(int i = 1; i <= itemNum; i++)
cin >> item[i].itemPrice >> item[i].itemValue;
for(int i = 1; i <= itemNum; i++){
for(int j = totalMoney; j >= 0; j--){
if(j >= item[i].itemPrice) value[j] = MAX(value[j], value[j - item[i].itemPrice] + item[i].itemPrice * item[i].itemValue);
}
}
cout << value[totalMoney] << endl;
}

#include<stdio.h>
#include<string.h>
int v[10000],p[10000],d[26][30001];
int main()
{
int i,j,k,n,m;
scanf("%d%d",&n,&m);
int w[m+1];
for(i=0;i<m;i++)w[i]=0;
//memset(w,0,sizeof(w));
for(i=0;i<m;i++)
{
scanf("%d%d",&v[i],&p[i]);
w[i]=v[i]*p[i];
}
//memset(d,0,sizeof(d));
for(i=m-1;i>=0;i--)
{
for(j=0;j<=n;j++)
{
d[i][j]=(i==m-1?0:d[i+1][j]);
if(j>=v[i])d[i][j]=d[i][j]>d[i+1][j-v[i]]+w[i]?d[i][j]:d[i+1][j-v[i]]+w[i];
}
}
printf("%d",d[0][n]);
return 0;
}
逆推的顺序

#include <iostream>
#include <algorithm>
using namespace std;

int dp[26][30001], w[MAXL], p[MAXL];

int main()
{
int V, n;
cin >> V >> n;
for (int i = 1; i <= n; i++)
{
cin >> w[i] >> p[i];
p[i] *= w[i];
}

for (int i = 1; i <= n; i++)
{
for (int j = V; j > 0; j--)
{
if (j >= w[i])
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + p[i]);
else
dp[i][j] = dp[i - 1][j];
}
}
cout << dp[n][V] << endl;
}

#include<cstdio>
#include<iostream>
using namespace std;
int i,j,p[30],v[30],n,m,f[30010];
int main()
{
cin>>n>>m;
for(i=1;i<=m;i++)
cin>>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];
cout<<f[0];
return 0;
}

这是一道01背包问题，只不过稍稍做了改动，即把价值藏了起来，变为重要度和价格乘积罢了。总钱就是容量，价格是体积。不是难题。

推荐和小飞侠的游园方案和采药一起写，这样刚好练习巩固01背包，因为01背包最基础也最重要。

###block code
program P1317;
uses math;
var data:array[0..30000] of longint;
n,m,v,p,sum,i,j:longint;
begin
fillchar(data,sizeof(data),0); read(n,m);
for i:=1 to m do //直接读取价格和等级，不存，省空间。
begin
read(v,p); sum:=v*p; //价值就是2个数乘积
for j:=n downto v do
data[j]:=max(data[j],data[j-v]+sum); //01背包的动态转移方程
end;

write(data[n]); //答案
end.

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

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.

编译成功

foo.pas(15,17) Warning: Variable "f" does not seem to be initialized
测试数据 #0: Accepted, time = 0 ms, mem = 1176 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1172 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1172 KiB, score = 10
测试数据 #3: Accepted, time = 11 ms, mem = 1168 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 1172 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 1168 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 1172 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 1168 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1168 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 1168 KiB, score = 10
Accepted, time = 71 ms, mem = 1176 KiB, score = 100