Description
llk经常和wy一起去yh小饭馆吃盖浇饭，一天他们吃完后llk把两个人的钱一起付了，但是wy不想欠llk的钱。现在wy手中有一些散钱，llk手中也有一些散钱，wy想知道能不能刚好使得两不相欠，但是wy很笨，你能帮助wy吗？
Input
多组测试数据，每组第一行输入3个非负整数，C，n，m。C代表wy欠llk的钱，n代表wy手中钱面值的种类，m代表llk手中钱面值的种类。接下来的n行，每行两个数v， c，分别代表wy手中面值为v的钱币有c个。再接下来的m行，每行两个数v，c，分别代表llk手中面值为v的钱币有c个。 （C <= 10000; 1<=n, m<50; 0<=v < =100; 0<=c<=10 ）
Output
每组数据输出一行，如果存在一种方案使得wy和llk两不相欠，输出YES，否则输出NO。
Sample Input
7 1 1
10 1
1 10
思路：多重背包记录dp的存在性。设p[]为wy的可能凑到钱，q[]为llk可能凑到的钱，分别dp一遍，求是否存在p[i]==q[i-c]==1即可。
dp状态: dp[i]即是否能凑到 金额为 i 的钱
dp转移: dp[j] |= dp[j-k*v[i]
#include <math.h>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <set>
#include <algorithm>
#define ll long long
#define Inf 0x3f3f3f3f
using namespace std;
const int maxn=5e5+5;
struct node{
int v,c;
};
node a[55],b[55];
int p[50050];
int q[50050];
int main()
{
int c,n,m;
while(cin>>c>>n>>m){
memset(p,0,sizeof(p));
memset(q,0,sizeof(q));
int sum=0;
for(int i=1;i<=n;i++){
cin>>a[i].v>>a[i].c;
sum+=a[i].v*a[i].c;
}
p[0]=q[0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=a[i].c;j++){
for(int k=a[i].v*j;k<=sum;k++){
p[k]|=p[k-a[i].v*j];
}
}
}
sum=0;
for(int i=1;i<=m;i++){
cin>>b[i].v>>b[i].c;
sum+=b[i].v*b[i].c;
}
for(int i=1;i<=m;i++){
for(int j=0;j<=b[i].c;j++){
for(int k=b[i].v*j;k<=sum;k++){
q[k]|=q[k-b[i].v*j];
}
}
}
int flag=0;
for(int i=c;i<=50000;i++){
if(p[i]==1&&q[i-c]==1){
flag=1;break;
}
}
if(flag) printf("YES\n");
else printf("NO\n");
}
}
然后有一道类似的可以使用背包+贪心做的题。
Codeforces Round #637 (Div. 2) -D
题意大概就是，一段LED段有些块坏了，你现在只能且必须修好其中k个块，不多不少。问修好之后最大能显示最大的数是多少。思路：也是可以转化成背包存在性的问题。对于每一个LED，我们对其可以修改到的数字进行判断，比如0->8消耗1，1->7消耗1，当然有些情况是不能修改的，比如1->5这样的，对每一个LED求完之后就可以转化为背包问题了：
从后往前dp，看能否dp[0] [0] == 1。如果为0，则肯定不存在这样的背包，出-1。如果存在的话，从前往后从9-0的优先顺序看符合的情况。所以本质上，类似对背包的路径取优。
为什么不是从前往后dp ：我们最后的贪心取法是从前往后取，从后往前的dp才是符合背包的通路的（证明当前点肯定可以到达末点）
dp状态：dp [i] [j] 指是否存在到第 i 个片段，花费 j 的情况
dp转移：dp[i] [j-cnt] |= dp[i+1] [j];
#include <iostream>
#include <cstdio>
#include <string.h>
#include <math.h>
#include <queue>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#define ll long long
#define Inf 0x3f3f3f3f
using namespace std;
const int maxn=2e3+5;
int n,k;
string t[10]={
"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"
};
string s[maxn];
struct node{
int cost,v;
};
vector<node>g[maxn];
int dp[maxn][maxn];
int main()
{
cin>>n>>k;
//for(int i=0;i<n;i++) cin>>s[i];
for(int i=0;i<n;i++){
cin>>s[i];
for(int j=9;j>=0;j--){
int cnt=0,flag=1;
for(int k=0;k<7;k++){
if(s[i][k]=='1'&&t[j][k]=='0'){
flag=0;break;
}
cnt+=(s[i][k]=='0'&&t[j][k]=='1');
}
if(flag) g[i].push_back({cnt,j});
}
}
//初始值置1
dp[n][k]=1;
for(int i=n-1;i>=0;i--){
for(int j=0;j<g[i].size();j++){
int cnt=g[i][j].cost,val=g[i][j].v;
for(int p=cnt;p<=k;p++){
dp[i][p-cnt]|=dp[i+1][p];
}
}
}
if(!dp[0][0]){
printf("-1\n");
return 0;
}
int cnt=0;
//贪心-从9-0的顺序取最优解
for(int i=0;i<n;i++){
for(int j=0;j<g[i].size();j++){
if(cnt+g[i][j].cost>k) continue;
if(dp[i+1][cnt+g[i][j].cost]){
printf("%d",g[i][j].v);
cnt+=g[i][j].cost;
break;
}
}
}
printf("\n");
return 0;
}