題意：給你c（2<=c<=20）個掛鉤，g（2<=g<=20）個砝碼，求在將所有砝碼（砝碼重1~~25）掛到天平(天平長? -15~~15)上，并使得天平平衡的方法數(shù).......

思路：（這是我木有想到的）將g個掛鉤掛上的極限值：15*25*20==7500

那么在有負(fù)數(shù)的情況下是-7500~~7500?? 以0為平衡點(diǎn)......

那可以將平衡點(diǎn)往右移7500個單位，范圍就是0~~15000......這樣就好處理多了

其實(shí)我覺得以后的題目中不僅僅天平問題可以這樣處理，在有負(fù)數(shù)的以及要裝入數(shù)組處理的題目中，我們都可以嘗試著平移簡化問題......

這題目是要將所有的砝碼都掛到天平上后的最多方法數(shù)，同時砝碼自帶質(zhì)量，也就是說，這不僅僅有著“容量”的限制，還有著“件數(shù)”的限制，很明顯的二維費(fèi)用背包......

每個砝碼只能用一次，果斷01背包，并且在處理這一狀態(tài)前，先判斷前一狀態(tài)是否存在......我喜歡用>0表示存在，用0表示不存在，而這個題目又是求方法數(shù)，不需要再減去1........

#include<iostream> #include<stdio.h> #include<string.h> using namespace std; int dp[25][16000],s[25],t[25]; int main() {int n,m;while(scanf("%d %d",&n,&m)>0){for(int i=1;i<=n;i++){scanf("%d",&s[i]);}for(int i=1;i<=m;i++)scanf("%d",&t[i]);memset(dp,0,sizeof(dp));dp[0][7500]=1;int sum=0;for(int i=1;i<=m;i++) //m個砝碼 {for(int j=15000;j>=1;j--) //01背包，每個砝碼只能用一次 for(int k=1;k<=n;k++)if(j+s[k]*t[i]>=0&&j+s[k]*t[i]<=15000&&dp[i-1][j+s[k]*t[i]]) //判斷前一狀態(tài)是否存在........ {dp[i][j]+=dp[i-1][j+s[k]*t[i]];//printf("j==%d dp==%d %d\n",j,dp[i][j],j+s[k]*t[i]);}//sum++;}printf("%d\n",dp[m][7500]);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的dp之二维背包poj1837(天平问题 推荐)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。