欠债还钱、CodeforcesRound#637(Div.2)-D（多重背包）LanguhZ的博客-

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("YESn"); else printf("NOn"); } } 

然后有一道类似的可以使用背包+贪心做的题。
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("-1n"); 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; }