01背包问题，做时间

经典的01背包.......

怎么没头像

渣渣

so water 太水了
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=10001,maxm=1001;
int t,m;//t表示时间，m表示种类
int c[maxn][maxm];
int a[maxn],b[maxm];
int main()
{
cin>>t>>m;
for(int i=1;i<=m;i++)
cin>>a[i]>>b[i];
for(int i=1;i<=m;i++)
for(int j=t;j>0;j--)
if(a[i]<=j) c[i][j]=max(c[i-1][j],c[i-1][j-a[i]]+b[i]);
else c[i][j]=c[i-1][j];
cout<<c[m][t];
return 0;
}

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int w[101],c[101],a[1001];
int main()
{
int t,m,i,j;
scanf("%d%d",&t,&m);
for (i=1;i<=m;i++)
scanf("%d%d",&w[i],&c[i]);
for (i=1;i<=m;i++)
for (j=t;j>=w[i];j--)
a[j]=max(a[j],a[j-w[i]]+c[i]);
printf("%d",a[t]);
return 0;
}

/*
发布者：可怕的熊真是可怕（xuxiaojian）
今天心情大好，发个题解助助兴，哈哈
*/
//本题乃01背包最经典的题目，只有取和不取两种情况哈
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;

int t,n,w[1005],p[1005],c[105][1005];

int main(){
memset (c,0,sizeof c);//数组初始化
scanf ("%d %d",&t,&n);
for (int i=1;i<=n;i++){
scanf ("%d %d",&w[i],&p[i]);//读入（由于本题样例小，就不加读入优化了）
}
for (int i=1;i<=n;i++){
for (int j=t;j>=1;j--){//从T到1
if (j>=w[i]) c[i][j]=max(c[i-1][j],c[i-1][j-w[i]]+p[i]);//01背包动态转移方程
else c[i][j]=c[i-1][j];
}
}
printf ("%d",c[n][t]);//打印结果
return 0;
}

py党来一个
```python
import re
import sys

def readln():
return map(int, input().split())

def readarray():
s = input()
k = []
r = [0,]
k = re.split(' ',s)
for i in k:
r.append(int(i))
return r

def write(e,ed):
for i in e:
print(i,end=ed)
print()

t,n = readln()
a = [0 for i in range(0,t+1)]
for i in range(1,n+1):
ti,val=readln()
for j in range(t,ti-1,-1):
#write(a,' ')
if (a[j]<a[j-ti]+val):
a[j]=a[j-ti]+val
#write(a,' ')
print(a[t])
```

#include<cstdio>
using namespace std;
int dp[1001],w[300],v[300];
int main()
{
int t,m,w,v;scanf("%d%d",&t,&m);

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

#include <stdio.h>

#define MAX_M 100
#define MAX_T 1000
#define max(x, y) (x > y) ? x : y

int dp[MAX_M+1][MAX_T+1];

int main()
{
int T, M;
int t[MAX_M], v[MAX_M];

scanf("%d %d", &T, &M);
int x;
for (x = 0; x < M; x++)
scanf("%d %d", &t[x], &v[x]);

int i, j;
for (i = 0; i < M; i++)
for (j = 0; j <= T; j++)
{
if (j < t[i])
dp[i+1][j] = dp[i][j];
else
dp[i+1][j] = max(dp[i][j-t[i]]+v[i], dp[i][j]);
}

printf("%d", dp[M][T]);

return 0;
}

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int a[1000],b[1000],h;
int main()
{
//freopen("medic.in","r",stdin);
//freopen("medic.out","w",stdout);
int t,m,max=0;
cin>>t>>m;
for(int i=1; i<=m; i++)
{
cin>>a[i]>>b[i];
for (int j=1;j<=m;j++)
{
if(a[i]+a[j]==t)
{
h=b[i]+b[j];
if(h>max)
max=h;
}

}
}
cout<<max;
return 0;
}

#include<cmath>
#include<iostream>
using namespace std;
struct node{int time,weal;}a[194250];
int f[194][2500],s=0,t,i,j,n;
int main(){
cin>>t>>n;
for(i=1;i<=n;i++)cin>>a[i].time>>a[i].weal;
for(i=1;i<=n;i++)
for(j=0;j<=t;j++){
if(j>=a[i].time)f[i][j]=max(a[i].weal+f[i-1][j-a[i].time],f[i-1][j]);
else f[i][j]=f[i-1][j];
}

cout<<f[n][t];
return 0;
}

#include<stdio.h>
#include<stdlib.h>
int f[1001];
int main(){
// freopen("medic.in","r",stdin);
// freopen("medic.out","w",stdout);
int i,j,k,n,m,w;
scanf("%d%d",&w,&n);
for(i=1;i<=n;i++){
int a,b;
scanf("%d%d",&a,&b);
for(j=w;j>=1;j--)
if(j>=a &&f[j]<f[j-a]+b)f[j]=f[j-a]+b;
}
printf("%d\n",f[w]);
return 0;
}

#include <iostream>
using namespace std;
int f[1001],w[1001],v[1001];
int max(int x,int y){
    if(x>y) return x;
    return y;
}
int main(){
    int t,m,i,j;
    cin>>t>>m;
    for(i=1;i<=m;i++)
        cin>>w[i]>>v[i];
    for(i=1;i<=m;i++)
        for(j=t;j>=w[i];j--)
            f[j]=max(f[j-w[i]]+v[i],f[j]);
    cout<<f[t];
    return 0;
}

最短的程序来了！

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

program P1104;
var
    a:array[1..1000] of longint;
    i,j,n,t,t1,t2,m:longint;
begin
    readln(t,m);
    fillchar(a,sizeof(j),0);
    for i:=1 to m do
        begin
            readln(t1,t2);
            for j:=t-t1 downto 0 do if a[j]+t2>a[j+t1] then a[j+t1]:=a[j]+t2;
        end;
    writeln(a[t]);
end.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define N 1001
using namespace std;
int f[N],t[N],w[N];
int main()
{
int t1,m;
scanf("%d%d",&t1,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&t[i],&w[i]);
}

for(int i=1;i<=m;i++)
for(int j=t1;j>=t[i];j--)
{
f[j] = max(f[j],f[j-t[i]]+w[i]);

}
printf("%d\n",f[t1]);
return 0;
}

#include <iostream>
#include <vector>

using namespace std;

vector <int> f,c,w;

int main()
{
int n,m;
int i,j;
cin>>m>>n;
f.resize(m+1);
w.resize(n+1);
c.resize(n+1);
for(i=0;i<n;++i)
cin>>w[i]>>c[i];
for(i=0;i<=m;++i)
f[i]=0;
for(i=0;i<=n;++i)
for(j=m;j>=w[i];--j)
f[j]=max(f[j],f[j-w[i]]+c[i]);
cout<<f[m];
return 0;
}

简单dp
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
int t,m,s[104],z[104],dp[1100];
int main()
{
int i,j;
cin>>t>>m;
for(i=1;i<=m;i++)
{
cin>>s[i]>>z[i];
}
for(i=1;i<=m;i++)
{
for(j=t;j>=s[i];j--)
{
dp[j]=max(dp[j],dp[j-s[i]]+z[i]);
}
}
cout<<dp[t]<<endl;
return 0;
}

var
t,m,i,j,sj,jz:longint;
v:array[0..1000] of longint;
begin
readln(t,m);
for i:=1 to m do begin
readln(sj,jz);
for j:=t-sj downto 0 do if (v[j]+jz)>v[j+sj] then v[j+sj]:=v[j]+jz;
end;
writeln(v[t]);
end.

#include <iostream>
using namespace std;
int timedp[2000];
int yao[1500][4];
int main()
{
int n,time;
cin>>time>>n;
for(int i=1;i<=n;i++)
cin>>yao[i][1]>>yao[i][2];
for(int i=1;i<=n;i++)
for(int j=time;j>=yao[i][1];j--)
timedp[j]=max(timedp[j-yao[i][1]]+yao[i][2],timedp[j]);
cout<<timedp[time];
return 0;
}