代碼:
/* * Problem: UVA No.624 * Running time: 0MS * Complier: C++ * Author: javaherongwei * Create Time: 21:25 2015/9/8 星期二 * 【題意】你要錄制時間為N的帶子,給你一張CD的不同時長的軌道,求總和不大於N的錄制順序 【思路】要求總和最接近N,可以用01背包思想,把不同的軌道當成背包體積,求那麼問題可以 轉換為求總體積不超過N的最大價值,用二維數組記錄選過的數即可 */ #include#include using namespace std; const int N=10005; int volume[N]; int dp[N]; bool vis[25][N]; int main() { int n,V; while(scanf(%d%d,&V,&n)!=EOF) { memset(volume,0,sizeof(volume)); //input memset(dp,0,sizeof(dp)); memset(vis,0,sizeof(vis)); // vis true or not for(int i=0; i =volume[i]; --v) { if(dp[v]<=dp[v-volume[i]]+volume[i]) // != { dp[v]=dp[v-volume[i]]+volume[i]; vis[i][v]=1; //vis true } } } for(int i=n-1,j=V; i>=0; i--) { if(vis[i][j]) // if vis true,print the number { printf(%d ,volume[i]); j-=volume[i]; } } printf(sum:%d ,dp[V]); } return 0; }