Time Limit: 1 second
Memory Limit: 128 MB

【問題描述】

現有n個砝碼，重量分別為a1，a2，a3，……，an，在去掉m個砝碼后，問最多能稱量出多少不同的重量（不包括0）。?

【輸入格式】

輸入文件weight.in的第1行為有兩個整數n和m，用空格分隔 第2行有n個正整數a1，a2，a3，……，an，表示每個砝碼的重量。

【輸出格式】

輸出文件weight.out僅包括1個整數，為最多能稱量出的重量。

【數據規模】

對于20%的數據，m=0； 對于50%的數據，m≤1； 對于50%的數據，n≤10； 對于100%的數據，n≤20，m≤4，m＜n，ai≤100。

Sample Input1

3 1 1 2 2

Sample Output1

　3

【樣例說明】

在去掉一個重量為2的砝碼后，能稱量出1，2，3共3種重量。

【題解】

這是一個0/1背包+搜索的問題。

先選出m個物品，把他們"去掉“，然后對剩余的物品，進行0/1背包就可以了。

ai<=100,n<=20，則枚舉的最大重量為2000;

用一個boolean型的bo數組來表示某一個重量是否能達到。

if (can[j-w[i]])

can[j] = true;

最后統計一下重量的種數就可以了。

【代碼】

#include <cstdio> #include <cstring>int n,m,w[21],ma = 0; bool bo[21],can[2001]; //bo用來表示哪些砝碼可以用，can則表示哪些重量可以由砝碼稱出 void input_data() {scanf("%d%d",&n,&m);for (int i = 1;i <= n;i++)scanf("%d",&w[i]); }void select(int x,int num) //表示當前枚舉到了第x個砝碼，去掉的砝碼數量為num {if (num == m) //如果去掉的砝碼數量達到了要求，則進行一次0/1背包，求出能到達的重量 {memset(can,false,sizeof(can));can[0] = true;for (int i = 1;i <= n;i++)if (bo[i])for (int j= 2000;j>=w[i];j--) //0/1背包是逆序更新的。 if (can[j-w[i]])can[j] = true;int xx = 0;for (int j = 1 ;j <= 2000;j++)if (can[j]) //統計能夠到達的重量數目 xx++;if (xx > ma)ma = xx;return; }for (int i = x+1;i <= n;i++) //從x+1開始表示是一個組合問題,從n個中選出m個。 if (bo[i]){bo[i] = false;select(i,num+1);bo[i] = true; } }void get_ans() {memset(bo,true,sizeof(bo));select(0,0);//從0開始，可以包括m==0的情況。 }void output_ans() {printf("%d\n",ma); }int main() {freopen("stronger.in","r",stdin);freopen("stronger.out","w",stdout);input_data();get_ans();output_ans();fclose(stdin);fclose(stdout);return 0; }

轉載于:https://www.cnblogs.com/AWCXV/p/7632341.html

總結

以上是生活随笔為你收集整理的【u204】高级砝码称重的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。