一、题目描述

/problem/P1164

背包问题

二、思想

这道题不难，本来用滚动数组做是不想发题解了，但是又想试试用二维数组就发现了好多问题。(所以说一道题要尝试不同方法多做几遍)

状态定义 很简单 dp[i][j]:前i个菜，共有j元钱的方案数。

dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]]

当j==a[i] 时，dp[i][j]=dp[i-1][j]+1

j<a[i] 钱不够买不起第i道菜 dp[i][j]=dp[i-1][j]

前i个菜，共花j元钱的方案数 就等于j元钱只买 前i个菜 加上 买第i个菜 剩下的j-a[i] 元钱买 前i-1个菜。

首先这题不能拿常规的背包问题去求解，不然会死的很惨。

常规背包问题一般喜欢初始化 第一行 将第一个菜 在两种情况下枚举(钱够就1，不够为0)。

但是这道题目种明确说了钱要全部花完！这就意味者在只考虑一个菜的情况下，只有拥有钱=菜的价格 时 才算为一种方案。

所以 初始为 当拥有的钱 i等于第一道菜的价格dp[1][i]=1

再来一手滚动数组。

注意：从后往前推

只要注意初始化 dp[0]=1: 当菜的价格和拥有钱相等时 就是一种方案。

三、代码

#include <iostream>#include <cstdio>using namespace std;int dp[105][10005]={0};int main(){int n,m,a[105];scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=0;i<=m;i++) if(i==a[1]) {dp[1][i]=1;break;}for(int i=2;i<=n;i++){for(int j=0;j<=m;j++){if(j<a[i])dp[i][j]=dp[i-1][j];else if(j==a[i]) dp[i][j]=dp[i-1][j]+1;else dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]];}}printf("%d",dp[n][m]);return 0;}

滚动数组

#include <iostream>#include <cstdio>using namespace std;int dp[10005]={0};int main(){int n,m,a[105];scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);dp[0]=1;for(int i=1;i<=n;i++){for(int j=m;j>=0&&j>=a[i];j--){dp[j]+=dp[j-a[i]];}}printf("%d",dp[m]);return 0;}