Cash Machine
| Time Limit: 1000MS |
|
Memory Limit: 10000K |
| Total Submissions: 26954 |
|
Accepted: 9533 |
题目大意：有各种不同面值的货币，每种面值的货币有不同的数量，请找出利用这些货币可以凑成的最接近且小于等于给定的数字cash的金额。 多重背包转0 1背包 对于第 i 种货币可能的状态为w[ i ]到cash 状态方程 dp[j]=dp[ j-c[i] ]+w[i] （c[ i ] 表示”体积“ 实际上就是价值 等于w[ i ]便于区分 ） 用count[ i ]来记录n[ i ]中货币的使用次数 注意每次进入内循环之前（也就是更换货币之前都要将count 清0）
#include
#include
#include
#include
using namespace std; int main() { int cash,num,i,j; int n[15]; int w[15]; int dp[10001]; int count[10001]; while(cin>>cash>>num) { for(i=0;i
>n[i]>>w[i]; memset(dp,0,sizeof dp); for(i=0;i