1469：数据结构：简单背包问题

swanGooseMan 2021-08-13 原文

本题难点：简单背包问题递归程序的理解

简单背包问题
问题定义：
有一个背包重量是S，有n件物品，重量分别是W0,W1…Wn-1
问能否从这n件物品中选择若干件放入背包中使其重量之和正好为S

背包问题递归版本
解释：其选择只有两种可能，选择一组物品中包含Wn-1 ，此时knap(s,n)的解就是knap(s – Wn-1,n-1)的解
如果选择的物品中不包括Wn-1，这样knap(s,n)的解就是knap(s,n-1)的解
knap(s,n) = true, 当 s=0时
knap(s,n) = false ，当s < 0 或者 s > 0 且 n < 1
knap(s,n) = knap(s – Wn-1,n-1) || knap(s,n-1) 当s>0且n>=1

// 测试用例：
// 20 5
// 1 3 5 7 9
// 23 5
// 1 3 5 7 9
// 20 5
// 1 3 5 7 13

#include <iostream>
using namespace std;
bool knap(int s, int n, int w[])
{
    if (s == 0) return true; //递归出口 在s恰好为0时 递归结束
    if (s < 0 || (s > 0 && n < 0)) return false; //两种特殊情况
    if (knap(s - w[n - 1], n - 1, w))
    {
        //cout << w[n - 1] << " ";//输出重量之和正好为S的物品序列
        return true;
    }
    else  return knap(s, n - 1, w);
}
int main()
{
    //freopen("input.txt", "r", stdin);
    int S, n;
    while (~scanf("%d%d", &S, &n))//多组测试数据
    {
        int w[n];
        for (int i = 0; i < n; i++)
            scanf("%d", &w[i]);
        knap(S, n, w) ? printf("YES\n") : printf("NO\n");
    }
}