#include<iostream> using namespace std; //加入第i张时可以装满，dp[i][j]=dp[i-1][j-w[i]],不加入i张也可以装满，dp[i-1][j]; //dp[i][0]=true,dp[0][j]=false; //优化成一维数组。 int main(){ int value[16]={0,8,8,8,8,8,10,10,10,10,18,18,18,18,18,18}; int maxn=5*8+4*10+6*18; bool dp[maxn+1]; for(int i=0;i<=m...

#include<iostream> #include<cstdio> using namespace std; const int maxn=100; int weight[maxn]; int dp[maxn]; //每张邮票价值为1，求背包容量M,N个物品，装满的前提下获得最小的价值； //对于dp[i][j]来说， //（1）如果放入第i个物品可以填满j容量的背包，那么使用前i-1个物品可以填满j-w[i]容量的背包，于是dp[i][j]=dp[i-1][j-w[i]]+1； //（2）如果不放入第i个物品也可以填满j容量的背包,意味着只使用前i-1个...