poj 1276 Cash Machine（多重背包） - c++编程基础

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