CD UVA - 624 ————01背包（寻找路径）

客官°小女子只卖身不卖艺 2022-05-17 05:47 165阅读 0赞

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:

number of tracks on the CD. does not exceed 20  
no track is longer than N minutes  
tracks do not repeat  
length of each track is expressed as an integer number  
N is also integer  
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

**Input**  
Any number of lines. Each one contains value N, (after space) number of tracks and durations of the tracks. For example from first line in sample data: N=5, number of tracks=3, first track lasts for 1 minute, second one 3 minutes, next one 4 minutes

**Output**  
Set of tracks (and durations) which are the correct solutions and string “sum:” and sum of duration times.

**Sample Input**  
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  
**Sample Output**  
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

--------------------

这题让找的是01背包的路径，是一个很好的题，能够加深自己对背包问题的转移过程的理解，  
寻找背包路径的过程的重点代码：

for(int i=n-1;i>=0;i--)
                for(int j=W;j>=v[i];j--)
                    if(dp[j-v[i]]+v[i]>dp[j])
                    {
                        dp[j]=dp[j-v[i]]+v[i];//这道题价值和重量是一样的
                        vis[i][j]=1;    
                    }
            int j=W;//刚开始是最大重量的时候
            for(int i=0;i<n;i++)
            {
                if(vis[i][j])//如果物品被放入背包
                {
                    printf("%d ",v[i]);//按照正序输出（拿出）背包里物品的重量/价值
                    j -= v[i];  //让背包减去拿出去的物品
                }

--------------------

ACcode：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int MAXN=100000+7;
    int dp[MAXN];
    bool vis[25][MAXN];
    int n,W,v[MAXN];
    int main()
    {
        while(~scanf("%d %d",&W,&n))
        {
            for(int i=0;i<n;i++)
                scanf("%d",&v[i]);
            memset(dp,0,sizeof(dp));
            memset(vis,0,sizeof(vis));
            for(int i=n-1;i>=0;i--)
                for(int j=W;j>=v[i];j--)
                    if(dp[j-v[i]]+v[i]>dp[j])
                    {
                        dp[j]=dp[j-v[i]]+v[i];
                        vis[i][j]=1;    
                    }
            int j=W;
            for(int i=0;i<n;i++)
            {
                if(vis[i][j])
                {
                    printf("%d ",v[i]);
                    j -= v[i];  
                }   
            } 
            printf("sum:%d\n",dp[W]);
    
        }
        return 0;
    }