PAT甲级1068 Find More Coins (30 分)：[C++题解]DP、背包问题、dp输出方案

文章目录

• • 题目分析
  • 题目链接

题目分析

来源：acwing
分析：m是背包容量，$a_1,a_2,....,a_n$是n个物品，第i个物品的体积是$a_i$,恰好装满背包，且字典序最小的方案。

状态表示：$f[i][j]$表示只考虑前i个物品，总体积为j的选法是否存在。存在的话置为true，不存在的话置为false。

状态计算：
两种情况：不包含第i个物品：$f[i-1][j]$ ，意思是从1~i-1中选，面额是j，能不能凑出来，凑出来是true，凑不出来是false。

包含第i个物品：$f[i-1][j-a_i]$，意思是从1~i-1中选，面额是$j-a_i$,能不能凑出来。

由于要求输出最小的方案，这里需要对a数组进行从大到小排序。这样dp输出方案的时候是从小到大的。dp输出的原理是从最终的状态f[n][m]倒推的。

ac代码

#include<bits/stdc++.h> using namespace std;const int N =10010 , M = 110; //数量， 面额int n, m; int a[N]; bool f[N][M];int main(){cin >> n >> m;for(int i =1; i<= n; i++ ) cin >> a[i];//从大到小排序，这样dp输出方案的时候是从小到大。sort( a+1, a+n+1, greater<int>());f[0][0] = true;for(int i =1; i<= n; i++)for(int j =0; j<= m; j++){f[i][j] = f[i-1][j];if(j >= a[i]) f[i][j] |= f[i-1][j-a[i]]; //两种情况中的第二种}if(!f[n][m]) cout<<"No Solution"<<endl;else{bool is_first = true;while(n){if(m>=a[n] && f[n-1][m-a[n]]){if(is_first) is_first = false;else cout<<" ";cout << a[n];m -= a[n];}n--; }} }

题目链接

PAT甲级1068 Find More Coins (30 分)

总结

以上是生活随笔为你收集整理的PAT甲级1068 Find More Coins (30 分)：[C++题解]DP、背包问题、dp输出方案的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。