uva 624 CD (0/1背包)

点击打开链接uva 624

思路: 0/1背包
分析:
1 题目要求的是最大的时间，并且输出选择所选的磁带
2 要求最大的时间很容易，关键是怎么求所选的磁带。正常求0/1背包我们都是直接优化成一维即dp[j] = max(dp[j] , dp[j-v[i]]+w[i])，但是一维的话是不能记录路径的，所以这题应该利用二维即dp[i][j] = max(dp[i-1][j] , dp[i-1][j-v[i]]+w[i])
3 那么利用了二维之后，假设我们求出了ans = dp[n][sum]，那么我们可以通过回溯法求出路径。如果dp[n-1][sum] != dp[n][sum]说明取了第n个，那么到dp[n-1][sum-v[i]]......

代码:

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

const int N = 25;
const int MAXN = 10000;
int n , sum , v[N];
int dp[N][MAXN];

void solve(){
    memset(dp , 0 , sizeof(dp));
    int ans = 0;
    for(int i = 1 ; i <= n ; i++){
        for(int j = sum ; 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]);
        }
    }
    int i = n , j = sum;
    while(i&&n){
        if(dp[i-1][j] != dp[i][j]){ 
            printf("%d " , v[i]);
            j -= v[i];
        }
        i--; 
    }
    printf("sum:%d\n" , dp[n][sum]);
}

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