背包问题求解zsbd

Question

D31s9. 装物品方案（小内存）

时间限制：2.0s 内存限制：16.0MB Special Judge 代码提交间隔：5分钟(现在可以提交)
问题描述
有 件物品，第 件物品的重量为 （整数）。

对于给定的整数 ， 请选择一些物品，使得拼出的重量不超过 ，请问在此前提下能拼出的最大重量是多少？具体的方案是怎样的？

输入格式
输入的第一行包含一个整数 ，表示物品数量。

第二行包含 个整数 , , , ，分别为每个物品的重量。

最后一行包含一个整数 。

输出格式
输出的第一行包含一个整数 ，表示答案。

第二行包含一个整数 ，表示要选择的物品个数。

第三行包含 个整数，为每个选择的物品的编号，按照从小到大的顺序输出，相邻整数之间使用一个空格分隔。

样例输入
3
4 4 6
12
Data
样例输出
10
2
1 3
Data
以下答案也正确

10
2
2 3

这道背包问题我一开始打算用回溯做，但会超时和错误，现在打算还是老老实实用背包做，请各方神圣帮本蒟蒻看看吧！
急！在线蹲答案！
好回答立刻采纳！

Answer 1

01背包问题，可以使用动态规划处理，详细代码如下，望采纳

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int w[N], c[N];  // w[i] 表示第 i 件物品的重量，c[i] 表示当前可选的第 i 件物品的数量
int f[N][N];  // f[i][j] 表示在前 i 件物品中选择一些使得重量不超过 j 时的最大价值
int path[N];  // path[i] 表示第 i 个数在哪一行被更新

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &c[i]);
    scanf("%d", &m);

    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
            for (int k = 0; k <= c[i] && k * w[i] <= j; k ++ )
            {
                int val = f[i - 1][j - k * w[i]] + k * w[i];
                if (val > f[i][j])
                {
                    f[i][j] = val;
                    path[j] = i;
                }
            }

    printf("%d\n", f[n][m]);

    int k = m;
    while (k)
    {
        c[path[k]] -- ;
        k -= w[path[k]];
    }

    int res = 0;
    for (int i = 1; i <= n; i ++ )
        if (c[i]) res ++ ;

    printf("%d\n", res);
    for (int i = 1; i <= n; i ++ )
        if (c[i]) printf("%d ", i);

    return 0;
}