2024.11.28

DP

P1048 [NOIP2005 普及组] 采药 - 洛谷 | 计算机科学教育新生态

#include<iostream>
using namespace std;

int t[101], w[101];
int dp[1001];

int main(){

    int T, M;
    cin>>T>>M;
    for(int i=1; i<=M; i++){
        cin>>t[i]>>w[i];
    }
    for(int i=1; i<=M; i++){
        for(int j=T; j>=t[i]; j--){
            dp[j] = max(dp[j], dp[j-t[i]] + w[i]);
        }
    }
    cout<<dp[T]<<endl;

    return 0;
}

P1616 疯狂的采药 - 洛谷 | 计算机科学教育新生态

和上一题的不同的是，本题可以重复选一个物品

#include<iostream>
using namespace std;

int t[10001], w[10001];
long long dp[10000005];

int main(){

    int T, M;
    cin>>T>>M;
    for(int i=1; i<=M; i++){
        cin>>t[i]>>w[i];
    }
    for(int i=1; i<=M; i++){
        for(int j=t[i]; j<=T; j++){
            dp[j] = max(dp[j], dp[j-t[i]] + w[i]);
        }
    }
    cout<<dp[T]<<endl;

    return 0;
}