采药

#include <bits/stdc++.h>
using namespace std;
const int M = 1001;
int val[M], time_cost[M]; //存储给定草药的价值和花费时间
int f[M][M]; //第一维坐标表示对于第i个草药的取舍，第二维坐标表示所花费时间
//经典01背包，然而我只会用二维矩阵，令人感叹

int main (){
    int t1me, m;
    while (~ scanf ("%d %d", &t1me, &m)){
        for (int i = 1; i <= m; ++ i) scanf ("%d %d", &time_cost[i], &val[i]);
        for (int i = 1; i <= m; ++ i){
            for (int j = 1; j <= t1me; ++ j){
                f[i][j] = f[i - 1][j]; //首先默认舍去第i个草药
                if (j >= time_cost[i]){ // 如果当前时间不够采集第i个草药则跳过
                    f[i][j] = max(f[i][j], f[i - 1][j - time_cost[i]] + val[i]);
                    //在时间为j，考虑前i个草药的条件下，最大的值为f[i][j]
                }
            }
        }
    cout << f[m][t1me] << endl;
    }
    return 0;
}

//背包问题, 在把包装满的前提下求最大价值也就是最优解
#include<stdio.h>
int max(int a,int b){return a>b?a:b;}
struct beibao{
    int time;
    int value;
}num[100];
int main()
{     //n目标时间t药的种类
    int dp[1001],n,t,i,j;//dp[n]即时间为n时候的价值
    while(scanf("%d%d",&n,&t)!=EOF)
    {
        for(i=0;i<t;i++)//输入
            scanf("%d%d",&num[i].time,&num[i].value);
        for(int i=0;i<=n;++i)
            dp[i]=0;//初始化
          for(i=0;i<t;i++)//每个药
              for(j=n;j>=num[i].time;j--)
                    dp[j]=max(dp[j-num[i].time]+num[i].value,dp[j]);//要最大价值
            printf("%d\n",dp[n]);
    }
}

/*
    动态规划，01背包
    状态表示，f[i]表示i时间所能采摘的最大的价值
*/
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int t,m;
int v[maxn],w[maxn];
int f[maxn];
int main(){
	cin>>t>>m;
	for(int i=1;i<=m;i++) cin>>v[i]>>w[i];
	for(int i=1;i<=m;i++)
		for(int j=t;j>=v[i];j--)
			f[j] = max(f[j],f[j-v[i]]+w[i]);
	cout<<f[t]<<endl;
}

while True:
    try:
        t,m = list(map(int,input().split()))
        selects = []
        for i in range(m):
            selects.append(list(map(int,input().split())))
        values = [0] * (t+1)
        for i in range(m):
            if selects[i][0] <= t:
                for j in range(t,selects[i][0]-1,-1):
                    values[j] = max(values[j],values[j-selects[i][0]]+selects[i][1])
        print(values[t])
    except Exception:
        break

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int T = in.nextInt();
            int M = in.nextInt();
            int[][] arr = new int[M+1][2];
            for(int i=1;i<=M;i++){
                arr[i][0] = in.nextInt();
                arr[i][1] = in.nextInt();
            }
            int[][] dp = new int[M+1][T+1];
            for(int i=0;i<=T;i++){
                dp[0][i]=0;
            }
            for(int i=1;i<=M;i++){
                for(int j=0;j<=T;j++){
                    if(j<arr[i][0])
                        dp[i][j] = dp[i-1][j];
                    else
                        dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-arr[i][0]] + arr[i][1]);
                }
            }
            System.out.println(dp[M][T]);
        }
    }
}

#include<stdio.h>
#define MAX(a,b) (a>b?a:b)
int dp[1001];
char t[101], v[101];
int main() {
	int T, M;
	while (~scanf("%d%d", &T, &M)) {
		for (int i = 0; i < M; i++)scanf("%d%d", t + i, v + i);
		for (int i = 0; i <= T; i++)dp[i] = 0;
		for (int i = 0; i < M; i++) 
			for (int j = T; j >= t[i]; j--) 
				dp[j] = MAX(dp[j - t[i]] + v[i], dp[j]);
		printf("%d\n", dp[T]);
	}
	return 0;
}

经典01背包

#include <bits/stdc++.h>
using namespace std;

int main() {
  int t, m;
  cin >> t >> m;
  vector<int> value(m), weight(m);
  for (int i = 0; i < m; i++) {
    cin >> weight[i] >> value[i];
  }
  vector<int> dp(t + 1, 0);
  // 01背包
  for (int i = 0; i < m; i++) { // 物品
    for (int j = t; j >= weight[i]; j--) {  // 背包重量
      dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
  }
  cout << dp[t];
  return 0;
}

#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int dp[1020],mv[120],mcost[120];
    int t,m;
    while(cin>>t>>m){
        for(int i=0;i<m;i++){
            cin>>mcost[i]>>mv[i];
        }
        memset(dp, 0, sizeof(dp));
        for(int i=0;i<m;i++){
            for(int j=t;j>=mcost[i];j--){
                dp[j]=max(dp[j],dp[j-mcost[i]]+mv[i]);
            }
        }
        cout<<dp[t]<<endl;
    }
}
//和KY66点菜问题感觉基本一样

//ky75
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=1010;
int weight[MAXN],value[MAXN];
int dp[MAXN][MAXN];

int main(){
	int T,M;
	while(scanf("%d %d",&T,&M)!=EOF){
		for(int i=1;i<=M;i++){
			scanf("%d %d",&weight[i],&value[i]);
		}
		for(int i=0;i<=T;i++){
			dp[0][i]=0;
		}
		for(int i=0;i<=M;i++){
			dp[i][0]=0;
		}
		for(int x=1;x<=T;x++){
			for(int y=1;y<=M;y++){
				if(x<weight[y])
					dp[y][x]=dp[y-1][x];
				else
					dp[y][x]=max(dp[y-1][x],dp[y-1][x-weight[y]]+value[y]);
			}
		}
		printf("%d\n",dp[M][T]);
	}
}

while True:
    try:
        T, M = [int(i) for i in input().split()]
        values = [[] for i in range(M)]
        for i in range(M):
            values[i] = [int(i) for i in input().split()]
        
        dp = [[0 for i in range(T+1)] for _ in range(M+1)]
        
        for i in range(1, M + 1):
            for j in range(1, T + 1):
                #这里的i-1是因为我们的价值矩阵values从0开始索引的，不是代表第0件物品，注意细节
                if j - values[i - 1][0] >= 0:
                    value_with_i = values[i - 1][1] + dp[i-1][j - values[i - 1][0]]
                else:
                    value_with_i = 0
                value_without_i = dp[i - 1][j]
                dp[i][j] = max(value_with_i, value_without_i)
        print(dp[-1][-1])
        
        
    except:
        break

#include<iostream>
#include<cstdio>

using namespace std;

const int N = 1000 + 10;

int main(){
    int t, m, weight[N], value[N], dp[N];
    while(scanf("%d%d", &t, &m) != EOF){
        for(int i = 0; i < m; i++) scanf("%d%d", &weight[i], &value[i]);
        fill(dp, dp + t + 1, 0);
        for(int i = 0; i < m; i++){
            for(int j = t; j >= weight[i]; j--)
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
        printf("%d\n", dp[t]);
    }
    return 0;
}

#include<iostream>
using namespace std;
const int N = 1010;
int f[N];
int n, m;

int main(){
    while(cin >> m >> n){
        for(int i = 0, v, w; i < n; i ++ ){
            cin >> v >> w;
            for(int j = m; j >= v; j -- )
                f[j] = max(f[j], f[j - v] + w);
        }
        cout << f[m] << endl;
    }
    return 0;
}

while True:
    try:
        t, m = map(int,input().split())
        times = []
        values = []
        for _ in range(m):
            time, value = map(int,input().split())
            times.append(time)
            values.append(value)
        dp = [[0]* (t+1)  for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, t + 1):
                if times[i -1] > j:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = max(dp[i-1][j],values[i - 1] + dp[i - 1][j - times[i - 1]] )
        print(dp[-1][-1])
    except:
        break