suse oj 超市促销活动[完全背包]

suse oj 超市促销活动[完全背包]

超市促销活动[完全背包]_[校题]

题目描述

一个超市拿出n种商品搞促销活动，要求用户可以任选多件商品（注意：每种商品都库存充足，一个客户可以选多件相同商品），只要用户选择的商品能凑成988元，就可以500元带回家。
小明觉得这活动优惠力度太大，必须参加。
但是他有个问题想求助你：这些商品中，最少选几件就可以凑成988呢？会不会商家欺诈根本不能凑988？

输入

每组数据分两行：
第一行两个整数n和p，n种商品(1≤n≤100)，凑成活动价p元(1<=p<=100000)。
第二行输入n个数ai(1≤ai≤100)，表示每种商品的价格。
最后一行输入0，表示测试结束。

输出

输出最少选几件商品就可以凑成p元。如果无法凑成p元，输出"illegal"。

解题 当时校选拔时我思考的是dfs 枚举每一种方案 + 剪枝 妥妥的TLE
今天心血来潮从新翻开看了一下 发现是一道 可以用完全背包 来解的题
让我们康康原来的完全背包DP f x , y = m a x ( f x − 1 , y , f x , y − w [ i ] + v [ i ] ) f_x,_y = max(f_{x-1},_y,f_{x},_{y-w[i]}+v[i]) fx​,y​=max(fx−1​,y​,fx​,y−w[i]​+v[i])
简化完的 递推公式为 f x = m a x ( f x , f x − w [ t ] + v [ t ] ) f_x = max(f_x,f_{x-w[t]} +v[t]) fx​=max(fx​,fx−w[t]​+v[t])
这个公式跟我们这一到题的关系是什么呢？ 我们可以观察发现这一道题 每一个数可以取多次 并且让我们求最少取几个数来达到998 这样的数字 所以我们可以尝试递推 f x = m i n ( f x , f x − w [ y ] + 1 ) f_x = min(f_x,f_{x-w[y]}+1) fx​=min(fx​,fx−w[y]​+1) 就可以把这一道题解出来

代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 111;
const int M = 1e5+111;
int n,p;
int g[N];
int t[M];
int main(){while(1){scanf("%d",&n);if(!n) return 0;scanf("%d",&p);for(int i=0;i<=p;i++)t[i]=0;for(int i=1;i<=n;i++) scanf("%d",&g[i]),t[g[i]]=1;for(int i=1;i<=n;i++)for(int j=g[i];j<=p;j++)if(t[j-g[i]]||j==g[i]){if(j==g[i]) t[j]=1;else {if(t[j]) t[j] = min(t[j],t[j-g[i]]+1);else t[j]=t[j-g[i]]+1;}}if(t[p]) cout<<t[p]<<endl;else cout<<"illegal"<<endl;}return 0;
}