13031: 【原3031】露子的野餐

题目描述

author: sonicmisora 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/3031

【题目描述】

今天是个难得的风和日丽的星期天，你现在要去和露子吃野餐。你们一共带了n袋食物准备享用。但是不幸的事情发生了，你们到达草地时发现有的食物不见了。为了找出是哪些东西不见了，你们决定通过计算来解决。露子告诉你n袋食物每袋的重量，以及现在所有食物的总重量。为了能更开心地享受野餐，你掏出了电脑

【输入格式】

第一行有一个数m，表示当前有的食物的总重量。第二行有一个数n，表示出门时一共带了n袋食物。接下来一共有n行，每行表示第i号食物的重量Mi。

【输出格式】

输出仅包含一行：如果无解，请输出0；如果有多组解，请输出-1；否则，请按从小到大的顺序依次输出丢失的食物的编号，它们之间用空格隔开。

【样例输入】

【样例输出】

2 3

【数据规模】

1<=n<=100, 1<=Mi<=1000. 即总袋数小于等于100，每袋食物重量小于等于1000。每个测试点2s时限。

【提示】

使用动态规划解决。

WashSwang's solution

#include <iostream>
using namespace std;
int m,n,w[101],dp[101][100001],ans[101],ansn;
int main() {
    cin>>m>>n;
    for (int i=1;i<=n;++i) {
        cin>>w[i];
        m-=w[i];
    }
    m=-m;
    dp[0][0]=1;
    for (int i=1;i<=n;++i)
        for (int j = m; j >= 0; --j) {
            dp[i][j] = dp[i - 1][j];
            if (j>=w[i]) dp[i][j]+=dp[i - 1][j - w[i]];
        }
    if (dp[n][m]==0) cout<<0<<endl;
    else if (dp[n][m]>1) cout<<-1<<endl;
    else{
        ansn=0;
        for (int i=n;i>=1;--i)
            if (m>=w[i]&&dp[i - 1][m - w[i]]) {
                ans[ansn++] = i;
                m-=w[i];
            }
        for (int i=ansn-1;i>=0;--i)
            cout<<ans[i]<<' ';
    }
    return 0;
}