一道普通的背包问题

Jason_ 发布于 2022-02-10 21:24， 1474 次点击

题目描述
给定背包载重量W和物体种类N，以及每种物体的重量Wi，每种物体只有一个，问是能将背包正好装满的方案有多少种。
输入
两行数据第一行两个整数，w,n分别表示背包的总载重量和物品种类。（w＜５０００，n＜＝２０）
第二行 n个整数，分别表示每个物品的重量Wi（Wi＜＝２５０）
输出
输出一个整数表示正好装满的背包的方案数
样例
输入
10 5
1 2 3 4 5
输出
3

2 回复

rjsp2022-02-11 13:30

这种问题不如直接网上查

我只是好奇问问
如果输入
10 5
5 5 5 5 5
那应该输出多少？是输出1呢，还是10？

Jason_2022-02-13 09:12

回复 2楼 rjsp

去看了看网上还没有这样的代码自己写了一个
按照你这个输入应该是10

程序代码：

#include <bits/stdc++.h>
using namespace std;
int f[20001],w[101],n,m;
int main()
{
    cin>>m>>n;
    for (int i=1; i<=n; i++)
      cin>>w[i];
    f[0]=1;
    for (int i=1; i<=n; i++)
      for (int j=m; j>=w[i]; j--)
        f[j]=f[j]+f[j-w[i]];
    cout<<f[m];
    return 0;
}