动态规划入门——I NEED A OFFER!
转载请注明出处：http://blog.csdn.net/a1dark
分析：由于正向不是很好求、所以先求补集、然后用1-补集=本身、这样的话跟01背包就没多大差别了、
#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;#define N 10005double dp[N];int c[N];double w[N];int main(){ int n,m; while(scanf("%d%d",&n,&m)!=EOF){ if(n==0&&m==0)break; for(int i=0;i<m;i++) scanf("%d%lf",&c[i],&w[i]); memset(dp,0,sizeof(dp)); for(int i=0;i<m;i++){ for(int j=n;j>=c[i];j--) dp[j]=max(dp[j],(1-(1-dp[j-c[i]])*(1-w[i]))); } printf("%.1lf%%\n",dp[n]*100); } return 0;}