RQNOJ 开心的金明(0/1背包)

点击打开链接

思路：0/1背包

分析：

1 很明显的0/1背包

代码：

// 一维
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 30;
const int MAXN = 30010; 

int total , m;
int v[N] , w[N];
int dp[MAXN];

int solve(){
    for(int i = 1 ; i <= m ; i++){
        for(int j = total ; j >= v[i] ; j--)
           dp[j] = max(dp[j] , dp[j-v[i]]+v[i]*w[i]);  
    }
    return dp[total];
}

int main(){
    while(scanf("%d%d" , &total , &m) != EOF){
         for(int i = 1 ; i <= m ; i++)     
             scanf("%d%d" , &v[i] , &w[i]); 
         memset(dp , 0 , sizeof(dp));
         printf("%d\n" , solve());
    } 
    return 0;
}

// 二维
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;


const int N = 30;
const int MAXN = 30010; 

int total , m;
int v[N] , w[N];
int dp[N][MAXN];

int solve(){
    memset(dp , 0 , sizeof(dp));
    for(int i = 1 ; i <= m ; i++){
        for(int j = total ; j >= 0 ; j--){
            dp[i][j] = dp[i-1][j];
            if(j >= v[i])
                dp[i][j] = max(dp[i][j] , dp[i-1][j-v[i]]+v[i]*w[i]);  
        }
    }
    return dp[m][total];
}

int main(){
    while(scanf("%d%d" , &total , &m) != EOF){
        for(int i = 1 ; i <= m ; i++)     
            scanf("%d%d" , &v[i] , &w[i]); 
        printf("%d\n" , solve());
    } 
    return 0;
}