http://acm.timus.ru/problem.aspx?space=1&num=1244
背包題? 理解并不難
主要在于如果答案有多個(gè)要輸出 -1
一個(gè)答案的話要輸出結(jié)果?? 否則輸出 0
用 sum [ n ] 表示到 n 有幾條路徑
狀態(tài)轉(zhuǎn)移方程為?
if(sum[j-a[i]])//a[i]表示第i個(gè)數(shù)據(jù)的大小
{
??????? sum[j]=max(sum[j]+1,sum[j-a[i]]);
}
代碼及其注釋:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define LL long long using namespace std; const int N=100003; int sum[N];//到 N 有幾條路徑 int f[N];// 記錄第一次到此用了那個(gè)數(shù)據(jù) int a[103];// 數(shù)據(jù)大小 bool select[103];//是否用了 void Fselect(int x)//記錄用了哪幾個(gè)數(shù)據(jù) { while(x) { select[f[x]]=true; x=x-a[f[x]]; } } int main() { //freopen("data.txt","r",stdin); int K,n; while(scanf("%d %d",&K,&n)!=EOF) { memset(sum,0,sizeof(sum)); sum[0]=1; memset(select,false,sizeof(select)); int m=0; for(int i=1;i<=n;++i) { scanf("%d",&a[i]); if(sum[K]>1)//如果答案有多個(gè) 則無(wú)需再找 continue; m=min(m+a[i],K);//最大 for(int j=m;j>=a[i];--j) { if(sum[j]==0)//如果是求得第一條到此路徑 記錄用了哪一數(shù)據(jù) { f[j]=i; } if(sum[j-a[i]])//更新到此路徑數(shù)目 { sum[j]=max(sum[j]+1,sum[j-a[i]]); } } if(sum[K]==1) Fselect(K); } if(sum[K]==0) {printf("0\n");continue;} if(sum[K]>1) {printf("-1\n");continue;} for(int i=1;i<=n;++i) { if(!select[i]) printf("%d ",i); } printf("\n"); } return 0; }
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號(hào)聯(lián)系: 360901061
您的支持是博主寫作最大的動(dòng)力,如果您喜歡我的文章,感覺我的文章對(duì)您有幫助,請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長(zhǎng)非常感激您!手機(jī)微信長(zhǎng)按不能支付解決辦法:請(qǐng)將微信支付二維碼保存到相冊(cè),切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
