砝码称重.cpp

来自「背包类问题浅析和一些背包类问题的解答源程序。」· C++ 代码 · 共 28 行

#include <iostream>
using namespace std;

const int N = 6, M = 1003;
int w[N]={1,2,3,5,10,20}, n[N], tot=0;
bool can[M]={true};

int main(){
    int i, j, k, ans=0;
    for( i=0; i<N; ++i ){
         cin >>n[i];
         tot += n[i] * w[i];
    }
    
    for( i=0; i<N; ++i )
    for( j=n[i]; j; --j )
    for( k=tot; k>=w[i]; --k )
         can[k] = can[k] || can[k-w[i]];
    
    for( i=tot; i; --i )
         ans += can[i];
    
    cout <<"Total=" <<ans <<endl;
    
    system( "pause" );
    return 0;
}