var
t,m,i,j,ans:longint;
p,v,dp:array[0..1000]of longint;
begin
readln(t,m);
fillchar(dp,sizeof(dp),0);
ans:=0;
for i:=1 to m do
readln(p[i],v[i]);
for i:=1 to m do
for j:=t-p[i] downto 0 do
if (dp[j]+v[i]>dp[j+p[i]]) then
dp[j+p[i]]:=dp[j]+v[i];
for i:=1 to t do
if dp[i]>ans then ans:=dp[i];
write(ans);
end.
快速刷水

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int M;//个数
int T;//时间
int w[1000]={0};//存价值
int c[1000]={0};//存时间

int fx[1000]={0};//表示前i件物品放入背包容量的最大值

int main(){
int i,j;
cin>>T>>M;

for(i=1;i<=M;i++){
cin>>c[i]>>w[i];
}
for(i=1;i<=M;i++){
for(j=T;j>=c[i];j--)
//fx[j]=fx[j]>fx[j-c[i]]+w[i]?fx[j]:fx[j-c[i]]+w[i];
fx[j]=max(fx[j],fx[j-c[i]]+w[i]);
}
cout<<fx[T]<<endl;
return 0;
}

数组少开1，分数少70

#include <cstdio>

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

int main(){
//  freopen("in.txt","r",stdin);
    int n,v;
    int c[1000],w[1000];
    int f[1001]={0};
    scanf("%d%d",&v,&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&c[i],&w[i]);
    for(int i=1;i<=n;i++)
        for(int j=v;j>=c[i];j--)
            f[j]=max(f[j],f[j-c[i]]+w[i]);
    printf("%d",f[v]);
    
    return 0;
}

水题
#include <iostream>
#include <cmath>
using namespace std;
int F[101][1001];
int L[101],T[101];
int n,mt;
int main()
{
cin>>mt>>n;
for(int i=1;i<=n;i++)
cin>>T[i]>>L[i];
for(int i=1;i<=n;i++)
{
for(int t=mt;t>=1;t--)
{
if(T[i]<=t) F[i][t]=max(F[i-1][t],F[i-1][t-T[i]]+L[i]);
else F[i][t]=F[i-1][t];
}
}
cout<<F[n][mt];
return 0;
}

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

int t, m, c[100], w[100], f[1001];

int main()
{
    scanf("%d%d", &t, &m);
    for (int i = 0; i < m; ++i) {
        scanf("%d%d", c + i, w + i);
    }
    for (int i = 0; i < m; ++i) {
        for (int v = t; v >= c[i]; --v) {
            f[v] = max(f[v], f[v - c[i]] + w[i]);
        }
    }
    printf("%d", f[t]);
    return 0;
}

#include<iostream>
#include<cstring>
using namespace std;
int bagsize, n, maxjiazhi[1001][1001];
struct baowu
{
int zhong, jiazhi;
};
baowu a[1001];
int max(int a, int b)
{
if (a >= b)
return a;
else
return b;
}
void input()
{
int temp;
cin >> bagsize >> n;
for (temp = 1; temp <= n; temp++)
{
cin >> a[temp].zhong >> a[temp].jiazhi;
}
}
void chu()
{
memset(maxjiazhi, 0, sizeof(maxjiazhi));
}
void getmax()
{
int x, y, temp1, temp2;
for (x = 1; x <= bagsize; x++)
{
for (y = 1; y <= n; y++)
{
if (x < a[y].zhong)
maxjiazhi[y][x] = maxjiazhi[y - 1][x];
else
{
temp1 = maxjiazhi[y - 1][x];
temp2 = maxjiazhi[y - 1][x - a[y].zhong] + a[y].jiazhi;
maxjiazhi[y][x] = max(temp1, temp2);
}
}
}
}
int main()
{
int i, temp;
input();
chu();
getmax();
cout << maxjiazhi[n][bagsize]<<endl;
return 0;
}

var
f,a,b:array [0..1005] of longint;
v,n,i,j,ans:longint;
begin
read(v,n);
for i:=1 to n do read(a[i],b[i]);
for i:=1 to n do
for j:=v-a[i] downto 0 do
if (f[j+a[i]]<f[j]+b[i]) then f[j+a[i]]:=f[j]+b[i];
ans:=0;
for i:=0 to v do if f[i]>ans then ans:=f[i];
writeln(ans);
end.

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int t,m,w,max,max1=0;
    int tl[100]={0};
    int wl[100]={0};
    int v[100][100]={0};
    scanf("%d",&t);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&tl[i]);
        scanf("%d",&wl[i]);
    }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=t;j++)
        {
            if(j>=tl[i])
            {
                if(v[i-1][j-tl[i]]+wl[i]>v[i-1][j])
                    v[i][j]=v[i-1][j-tl[i]]+wl[i];
                if(v[i-1][j]>=v[i-1][j-tl[i]]+wl[i])
                    v[i][j]=v[i-1][j];
            }
            else v[i][j]=v[i-1][j];
        }
        for(int i=1;i<=m;i++)
        {
           for(int j=1;j<t;j++)
           {
               if(v[i][j]>v[i][j+1])
                   max=v[i][j];
               else 
                   max=v[i][j+1];
           }
           if(max>max1) max1=max;
        }
           printf("%d",max1);
           return 0;
}

P1104采药Wrong Answer
标签：NOIP普及组2005[显示标签]
编译成功

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

#include<iostream>
#include<cstdio>
int f[1003],n,m;
using namespace std;
int main()
{
int x,y;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
for(int j=n;j>=x;j--)
{
if(f[j-x]+y>f[j])
f[j]=f[j-x]+y;
}
}
cout<<f[n];
}

在此献上python代码
a = [int(i) for i in raw_input().split()]
value = [0]
for i in range(1,100000):
value.append(-1)
for i in range(1,a[1]+1):
b = [int(j) for j in raw_input().split()]
c = range(0,a[0]+1)
c.reverse()
for j in c:
if value[j]+b[1]>value[j+b[0]]:
value[j+b[0]] = value[j] + b[1]
ma = -1
c = range(0,a[0]+1)
c.reverse()
for i in c:
if value[i] > ma:
ma = value[i]
print ma

//裸奔01背包-。-
#include <stdio.h>

const int MAXT=1000;
int dp[MAXT+1];

int main()
{
int t,m;
int time,value;
scanf("%d%d",&t,&m);
for(int i=0;i<m;i++)
{
scanf("%d%d",&time,&value);
for(int j=t;j>=time;j--)
{
dp[j]=dp[j]>dp[j-time]+value?dp[j]:dp[j-time]+value;
}
}
printf("%d\n",dp[t]);
return 0;
}

#include <iostream>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
const int N = 10005;
int f[N][N],t[N],v[N],time,n;
int main()
{

scanf("%d%d",&time,&n);
for(int i= 1;i <= n;i++){
scanf("%d%d",&t[i],&v[i]);
}
for(int i = 1;i <= n;i ++){
for(int j = time;j >= 0;j --){
f[i][j] = j >= t[i] ? max(f[i - 1][j - t[i]] + v[i],f[i - 1][j]) : f[i - 1][j];
}
}
printf("%d",f[n][time]);
return 0;
}

简单01背包的DP
###Pascal Code
program p1104;
var
f:array[0..101,0..1001] of longint;
v,w:array[0..101] of longint;
n,m,i,j:longint;
function max(a,b:longint):longint;
begin
if a>b then max:=a
else max:=b;
end;
procedure work;
begin
for i:=1 to n do
for j:=1 to m do
if j>=v[i]
then f[i,j]:=max(f[i-1,j],f[i-1,j-v[i]]+w[i])
else f[i,j]:=f[i-1,j];
end;
begin
readln(m,n);
for i:=1 to n do
read(v[i],w[i]);
work;
writeln(f[n,m]);
end.

简单dp
var
v,n,i,j:integer;
w,t,f:array[0..10000]of longint;
begin
readln(v,n);
for i:=1 to n do
readln(t[i],w[i]);
fillchar(f,sizeof(f),0);
for i:=1 to n do
for j:=v downto t[i] do
if f[j]<f[j-t[i]]+w[i]
then f[j]:=f[j-t[i]]+w[i];
writeln(f[v]);
end.

一A

#include <cstdio>
#include <algorithm>
#define MAX_T 1100
#define MAX_M 150
using namespace std;
int dp[MAX_T],T,M;
int v[MAX_M],w[MAX_M];
int main(){
scanf("%d%d",&T,&M);
for(int i = 0;i < M;++i){
scanf("%d%d",&w[i],&v[i]);
}
for(int i = 0;i < M;++i){
for(int j = T;j >= w[i];--j){
dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
}
}
printf("%d\n",dp[T]);
return 0;
}

简单~感觉这道题自己解得蛮巧妙的。
代码：
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
//freopen("medic.in","r",stdin);
//freopen("medic.out","w",stdout);
int m,n,i,v;
int w[101],c[101],f[1001]={0};
cin>>m>>n;
for(i=1;i<=n;i++)
cin>>w[i]>>c[i];
for(i=1;i<=n;i++)
for(v=m;v>=w[i];v--)
if(f[v]<f[v-w[i]]+c[i])
f[v]=f[v-w[i]]+c[i];
cout<<f[m];
return 0;
}

program a1;
var i,tmp,t,m:longint;
s,j:array[1..100]of longint;
f:array[0..100,0..1000]of longint;

function max(tmp,y:longint):longint;
begin
if tmp>y then max:=tmp else
max:=y;
end;

begin
readln(t,m);
for i:=1 to m do
readln(s[i],j[i]);
for i:=1 to m do
for tmp:=1 to t do
begin
if tmp>=s[i] then
f[i,tmp]:=max(f[i-1,tmp-s[i]]+j[i],f[i-1,tmp]);
end;
writeln(f[t,m]);
end.

#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)
scanf("%d %d",c+i,w+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我好菜

var f:array[0..1001,0..1001]of longint;
w,v:array[1..5000]of integer;
t,m,j,i:longint;
begin
readln(t,m);
for i:=1 to m do read(w[i],v[i]);
for i:=1 to t do f[0,i]:=0;
for i:=1 to m do f[i,0]:=0;
for i:=1 to m do
for j:=1 to t do begin
f[i,j]:=f[i-1,j];
if j>=w[i] then
if f[i-1,j]<=f[i-1,j-w[i]+v[i] then f[i,j]:=f[i-1,j-w[i]]+v+[i];
end;
write(f[m,t]);
end.

简单的01背包的题，算是基础的。
#include<iostream>
#include<cstdio>
using namespace std;
int max(const int&a,const int&b)
{
if(a>b)return a;
else{
return b;
}
}
int main()
{
int m,n,i,j,v,w[101],c[1001],f[101][1001];
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++){
scanf("%d%d",&w[i],&c[i]);
}
for(i=1;i<=n;i++){
for(v=m;v>=1;v--){
if(w[i]>v){
f[i][v]=f[i-1][v];
}
else{
f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]);
}
}
}
printf("%d",f[n][m]);
}