东东开车了（01背包回溯）

Olivia ·

更新时间:2024-09-21

· 878 次阅读

完整代码

东东开车出去泡妞(在梦中)，车内提供了 n 张CD唱片，已知东东开车的时间是 n 分钟，他该如何去选择唱片去消磨这无聊的时间呢

假设:

CD数量不超过20张
没有一张CD唱片超过 N 分钟
每张唱片只能听一次
唱片的播放长度为整数
N 也是整数
我们需要找到最能消磨时间的唱片数量，并按使用顺序输出答案（必须是听完唱片，不能有唱片没听完却到了下车时间的情况发生）

Input

多组输入

每行输入第一个数字N, 代表总时间，第二个数字 M 代表有 M 张唱片，后面紧跟 M 个数字，代表每张唱片的时长例如样例一: N=5, M=3, 第一张唱片为 1 分钟, 第二张唱片 3 分钟, 第三张 4 分钟

所有数据均满足以下条件:

N≤10000
M≤20

Output

输出所有唱片的时长和总时长，具体输出格式见样例

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背包相比，多了一个回溯过程，要求得到放到背包中的物体。本题输出可能会有多种形式，输出任意一种即可。比如最后一组数据，可能会输出43 2 sum:45。

回溯过程的实现就是考虑当前dp[x][y]，如果dp[x][y]=dp[x-1][y]，那就说明没有选择第x个物品，回溯x-1, y。如果dp[x][y]=dp[x-1][y-w[i]]+v[i]，那么就说明选择了第x件物品，回溯x-1, y-w[i]。直到x和y有一方为0就返回。

完整代码

//#pragma GCC optimize(2)
//#pragma G++ optimize(2)
//#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn=20+1;
const int maxm=10000+1;
int n,m,a[maxn],dp[maxn][maxm];
int getint(){
    int x=0,s=1; char ch=' ';
    while(ch'9'){ ch=getchar(); if(ch=='-') s=-1;}
    while(ch>='0' && ch>n>>m){
        for (int i=1; i>a[i];
        for (int i=1; i<=m; i++)//普通01
            for (int j=0; j=a[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i]]+a[i]);
                else dp[i][j]=dp[i-1][j];
            }
        find(m,n);
        printf("sum:%d\n",dp[m][n]);
        memset(dp,0,sizeof(dp));
    }
    return 0;
}