UVA - 624
Time Limit: 3000MS | Memory Limit: Unknown | 64bit IO Format: %lld & %llu |
Description
You have a long drive by car ahead. You have a tape recorder, but unfortunately your best music is on CDs. You need to have it on tapes so the problem to solve is: you have a tape N minutes long. How to choose tracks from CD to get most out of tape space and have as short unused space as possible.
Assumptions:
Program should find the set of tracks which fills the tape best and print it in the same sequence as the tracks are stored on the CD
5 3 1 3 4 10 4 9 8 4 2 20 4 10 5 7 4 90 8 10 23 1 2 3 4 5 7 45 8 4 10 44 43 12 9 8 2
1 4 sum:5 8 2 sum:10 10 5 4 sum:19 10 23 1 2 3 4 5 7 sum:55 4 10 12 9 8 2 sum:45
Source
思路:01背包问题,就是把体积和重量看做了tracks和time,这里注意打印路径的方法
AC代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn= 10005; int dp[30][maxn], path[30][maxn]; int M, N; int ti[30]; void print(int a, int b) { if(a == 0) return; print(a - 1, path[a][b]); if(path[a][b] < b) printf("%d ", ti[a]); } int main() { while(scanf("%d", &M) != EOF) { scanf("%d", &N); for(int i = 1; i <= N; i++) { scanf("%d", &ti[i]); } memset(dp, 0, sizeof(dp)); for(int i = 1; i <= N; i ++) { for(int j = 0; j <= M; j ++) { dp[i][j] = dp[i - 1][j]; path[i][j] = j;//第i个不选时赋值为j; if(j >= ti[i]) { int tmp = dp[i - 1][j - ti[i]] + ti[i]; if(tmp > dp[i][j]) { dp[i][j] = tmp; path[i][j] = j - ti[i];//第i个选了时赋值为j - ti[i]; } } } } print(N, M);//递归打印路径 printf("sum:%d\n", dp[N][M]); } return 0; }
原文:http://blog.csdn.net/u014355480/article/details/44536387