这个作业的题解

老师，你要为忘记做作业却认真学习却做不出题目的同学们着想，不要删掉啊。

T1:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[10001];
int w[31],c[31];
signed main(){
    int m,n;
    scanf("%lld %lld",&m,&n);
    for(int i=1;i<=n;i++) scanf("%lld %lld",&w[i],&c[i]);
    dp[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=10000-c[i];j>=0;j--){
            if(dp[j]&&dp[j]+w[i]<=m+1){
                if(dp[j+c[i]]==0) dp[j+c[i]]=dp[j]+w[i];
                else dp[j+c[i]]=min(dp[j+c[i]],dp[j]+w[i]);
            }
        }
    }
    for(int i=10000;i>=0;i--){
        if(dp[i]){
            printf("%lld",i);
            return 0;
        }
    }
}

T2:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[10001];
int w[31],c[31];
signed main(){
    int m,n;
    scanf("%lld %lld",&m,&n);
    for(int i=1;i<=n;i++) scanf("%lld %lld",&w[i],&c[i]);
    dp[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=10000-c[i];j++){
            if(dp[j]&&dp[j]+w[i]<=m+1){
                if(dp[j+c[i]]==0) dp[j+c[i]]=dp[j]+w[i];
                else dp[j+c[i]]=min(dp[j+c[i]],dp[j]+w[i]);
            }
        }
    }
    for(int i=10000;i>=0;i--){
        if(dp[i]){
            printf("max=%lld",i);
            return 0;
        }
    }
}

T3:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define dis dp
int dp[6001];
signed main(){
	int n,m;
	scanf("%lld %lld",&n,&m);
	dp[0]=0;
	for(int i=1;i<=m;i++) dp[i]=-1;
	int ans=0;
	for(int i=1;i<=n;i++){
		int x,y,p;
		scanf("%lld %lld %lld",&x,&y,&p);
		for(int j=m;j>=x;j--){
			if(dp[j-x]!=-1){
				for(int k=1;k<=p;k++){
					if(j+(k-1)*x>m) break;
					if(dis[j+(k-1)*x]==-1) dis[j+(k-1)*x]=dis[j-x]+k*y;
					else dis[j+(k-1)*x]=max(dis[j+(k-1)*x],dis[j-x]+k*y);
					ans=max(ans,dis[j+(k-1)*x]);
				}
			}
		}
	}
	printf("%lld",ans);
	return 0;
}

T4:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[101][1001];
signed main(){
    int n,m;
    scanf("%lld %lld",&n,&m);
    int p;
    scanf("%lld",&p);
    for(int i=0;i<=100;i++) for(int j=0;j<=1000;j++) dp[i][j]=0x3f3f3f3f;
    dp[0][0]=0;
    int ans=0x3f3f3f3f;
    for(int iii=1;iii<=p;iii++){
        int u,v,w;
        scanf("%lld %lld %lld",&u,&v,&w);
        for(int i=100;i-u>=0;i--){
            for(int j=1000;j-v>=0;j--){
                if(dp[i-u][j-v]!=0x3f3f3f3f){
                    dp[i][j]=min(dp[i][j],dp[i-u][j-v]+w);
                    if(i>=n&&j>=m) ans=min(ans,dp[i][j]);
                }
            }
        }
    }
    printf("%lld",ans);
    return 0;
}

T5:

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    int n,m;
    scanf("%lld %lld",&n,&m);
    int dp[1000001];
    for(int i=1;i<=m;i++) dp[i]=-1;
    dp[0]=1;
    int x;
    for(int i=1;i<=n;i++){
        scanf("%lld",&x);
        for(int j=0;j+x<=m;j++){
            if(dp[j]!=-1){
                if(dp[j+x]==-1) dp[j+x]=dp[j];
                else dp[j+x]+=dp[j];
            }
        }
    }
    printf("%lld",dp[m]);
    return 0;
}